Matrix algebras in optimal preconditioning (Q5947456)

A class \(\mathbf V\) of complex matrices is introduced, along with a property called ``\((*)\)''. These concepts are used to help organize the theory of optimal preconditioners for use in conjugate gradient solution of linear Toeplitz systems. For the purpose of this paper, a preconditioner \(S\) for a matrix \(A\) is optimal if it well-approximates \(A\) and can be inverted using fast transforms. One objective of the authors is to systematize the choice of optimal preconditioners by characterizing the matrix algebras from which they are chosen. The class \(\mathbf V\) generalizes the classes of Hessenberg algebras and of \(h\)-spaces introduced by the authors and their colleagues. A subspace of complex matrices of dimension \(n\) of class \(\mathbf V\) is one for which a complex vector \(\mathbf v\) exists for each linear basis of matrices \(\{J_k\}\) so that \({\mathbf v}^TJ_k={\mathbf e}_k\) for \(k=1,\ldots,n\), where \({\mathbf e}_k\) denotes the vector whose \(k^{\text{ th}}\) component is unity and all the others are zero. Loosely speaking, a matrix of class \(\mathbf V\) is determined by a linear combination of its rows. A space of complex matrices is a ``\(*\)-space'' if the identity matrix is in the space and if its basis \(\{J_k\}\) satisfies the condition \[ J_i^HJ_j=\sum_{k=1}^n \overline{{[J_k]}}_{ij}J_k, \qquad 1\leq i,j \leq n \tag \(*\) \] The authors show that if a positive definite matrix \(A\) in a space \(\mathcal L\) of class \(\mathbf V\) satisfies condition \((*)\), then its best fit, \(S\), in the Frobenius norm is also positive definite. The authors also show that complex matrices \(X\) whose minimum and characteristic polynomials are equal are also characterized by the fact that the set of all polynomials in \(X\) is in class \(\mathbf V\). The authors go on to show that for several well-known matrix algebras, the least squares approximate to a given Toeplitz matrix can be found in \(O(n)\) operations. This is demonstrated by explicitly constructing the least squares approximate. Further, the least squares fit from matrix algebras \(\mu\) and \(\eta\) for a matrix \(A\) that is equal to a centrosymmetric Toeplitz plus Hankel matrix but with a low-rank perturbation can be computed in at most \(O(n\log n)\) arithmetic operations. The final sections of the paper are devoted to showing that least squares fits to positive definite Toeplitz matrices make good preconditioners for the conjugate gradients method because they tend to cluster the eigenvalues around 1. Numerical results are presented for a large set of test matrices, leading the authors to conclude that certain preconditioners are competitive with the best known Toeplitz preconditioners.