Some New Methods for Solving Linear Equations.

摘要

It takes of the order of N-cubed operations to solve a set of N linear equations in N unknowns. When the underlying physical problem has some time- or shift-invariance properties, the coefficient matrix is of Toeplitz (or difference or convolution) type and the equations can be with O(N-squared) operations. The authors have shown that with any nonsingular N x N matrix, the authors can associate an integer alpha between 1 and N such that it takes O(N-squared alpha operations to invert the matrix. The number alpha may be small for many non-Toeplitz matrices of physical interest. Some aspects of this result are discussed here, including extensions to continuous time kernels and integral equations. (Author)