An efficient preprocessor for solving systems of linear equations (Q4384043)

The paper proposes that in order to solve (1) \(Ax= b\) where \(A\) is a nonsingular matrix of order \(n\), (1) be replaced by (2) \(A^t A x= A^t b\). The authors note first that if \(A\) is a \(2\) by \(2\) block matrix with square blocks, then the computation of \(A^tA\) involves four similar matrix products plus two (arbitrary) matrix products, with their order halved. The arbitrary matrix products can be computed using Strassen's multiplication scheme that, for block matrices of order \(2\), needs the computation of only \(7\) products with the order in the blocks. In this way, the cost of computing \(A^tA\) is shown to be smaller than the one that would result if its symmetric structure wasn't taken into account. To solve (2), the authors propose then the application of Jacobi, Gauss-Seidel or SOR iterations; if convergence is obtained in \(O(n^2)\) operations, then the overall operational count becomes asymptotically smaller than the one resulting by application of Gaussian elimination to (1). The paper does not consider the problems that rounding error may cause when (1) is replaced by (2).