On 01/28/2018 05:58 PM, Richard B. Kreckel wrote:
In the first elimination step, Bareiss fraction free elimination produces a 3x3 submatrix where all elements have the common factor a11:
{{a11, a12, a13, a14}, { 0,a11*a22,a11*a23,a11*a24}, { 0, 0,a11*a33,a11*a34}, { 0, 0, 0,a11*a44}}
This is because the elements in the first column below the pivot element a11 are all zero.
It should be possible to use this observation and simply skip this fraction free elimination step! This would avoid the term growth if the elements below the pivot are all zero.
Of course, we mustn't divide by a11 in the next step (because it won't divide). And this won't work for determinant computation (because the determinant ends up in the lower right element with the Bareiss elimination). This was my thought as well. Turns out that not all of the factors can be eliminated this way. Consider a block-triangular matrix like this one:
{{a11, a12, a13, a14, a15}, {a21, a22, a23, a24, a25}, { 0, a32, a33, a34, a35}, { 0, 0, 0, a44, a45}, { 0, 0, 0, 0, a55}} If we'd just check for zero column under the pivot element, and skip the elimination operation along with subsequent division, we'll get this result: {{a11, a12, a13, a14, a15}, { 0, ..., ..., ..., ...}, { 0, 0, ..., ..., ...}, { 0, 0, 0, (a22*a11-a12*a21)*a44, (a22*a11-a12*a21)*a45}, { 0, 0, 0, 0, (a22*a11-a12*a21)*a55}} As you can see there's still an additional common factor. Now, I did found a way to remove all such factors by tracking them separately, but this costs 2 GCDs per pivot. It's faster than the original algorithm for sparse matrices, but still not as fast as Gauss, at least in my limited testing. See the attachment for the two modified Bareiss elimination schemes: one that only special-cases the zero column case, and the one that eliminates all the factors. Note: there's a paper titled "Fraction Free Gaussian Elimination for Sparse Matrices" [1], but I haven't yet took the time to see what sort of a modification are they using. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5429