Faster inversion and other black box matrix computations using efficient block projections
Wayne Eberly, Mark W. Giesbrecht, Pascal Giorgi, Arne Storjohann, Gilles Villard · 2007
Efficient block projections of non-singular matrices have recently been used by the authors in [10] to obtain an efficient algorithm to find rational solutions for sparse systems of linear equations. In particular a bound ofO~(n2.5) machine operations is presented for this computation assuming that the input matrix can be multiplied by a vector with constant-sized entries using O~(n) machine operations. Somewhat more general bounds for black-box matrix computations are also derived. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections of non-singular matrices, and this was only conjectured.