Matrix algebras in optimal preconditioning
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.
- \(h\)-space structure in matrix displacement formulas
- A practical algorithm to design fast and optimal band-Toeplitz preconditioners for Hermitian Toeplitz systems
- A Proposal for Toeplitz Matrix Calculations
- A unifying approach to some old and new theorems on distribution and clustering
- An Optimal Circulant Preconditioner for Toeplitz Systems
- Analysis of Preconditioning Techniques for Ill-Conditioned Toeplitz Matrices
- Circulant and Skewcirculant Matrices for Solving Toeplitz Matrix Problems
- Circulant Preconditioners for Hermitian Toeplitz Systems
- Closure, commutativity and minimal complexity of some spaces of matrices
- Conjugate Gradient Methods for Toeplitz Systems
- Displacement operator based decompositions of matrices using circulants or other group matrices
- Displacement structure approach to discrete-trigonometric-transform based preconditioners of G. Strang type and of T. Chan type
- Fast algorithms for the discrete W transform and for the discrete Fourier transform
- Fast Transform Based Preconditioners for Toeplitz Equations
- Hartley preconditioners for Toeplitz systems generated by positive continuous functions
- scientific article; zbMATH DE number 440685 (Why is no real title available?)
- scientific article; zbMATH DE number 3854346 (Why is no real title available?)
- scientific article; zbMATH DE number 4034981 (Why is no real title available?)
- scientific article; zbMATH DE number 3701511 (Why is no real title available?)
- scientific article; zbMATH DE number 3806227 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- Iterative methods for ill-conditioned Toeplitz matrices
- Matrix Algebras and Displacement Decompositions
- Matrix decompositions using displacement rank and classes of commutative matrix algebras
- Matrix displacement decompositions and applications to Toeplitz linear systems
- On a Matrix Algebra Related to the Discrete Hartley Transform
- On some properties of circulant matrices
- On the optimal computation of a set of symmetric and persymmetric bilinear forms
- On the Use of Certain Matrix Algebras Associated with Discrete Trigonometric Transforms in Matrix Displacement Decomposition
- Optimal and Superoptimal Circulant Preconditioners
- Optimal trigonometric preconditioners for nonsymmetric Toeplitz systems
- Permutation-matrix groups with positive sum
- Sine transform based preconditioners for symmetric Toeplitz systems
- Spectral and computational properties of band symmetric Toeplitz matrices
- Structure of algebras of commutative matrices
- The circulant operator in the Banach algebra of matrices
- Toeplitz Equations by Conjugate Gradients with Circulant Preconditioner
- Toeplitz Preconditioners for Toeplitz Systems with Nonnegative Generating Functions
- Which circulant preconditioner is better?
- A framework for polynomial preconditioners based on fast transforms. I: Theory
- A unifying approach to abstract matrix algebra preconditioning
- Efficient matrix preconditioners for black box linear algebra
- On a set of matrix algebras related to discrete Hartley-type transforms
- Hartley-type algebras in displacement and optimization strategies.
- Optimal rank matrix algebras preconditioners
- A variation of Broyden class methods using Householder adaptive transforms
- Algebras closed by \(J\)-Hermitianity in displacement formulas
- Adaptive matrix algebras in unconstrained minimization
- On uniform connectivity of algebraic matrix sets
- Low complexity matrix projections preserving actions on vectors
- Regularizing properties of a class of matrices including the optimal and the superoptimal preconditioners
- Gram matrices of fast algebras have a rank structure
- Locally X Matrices, Spectral Distributions, Preconditioning, and Applications
- Optimal Order Preconditioning of Finite Difference Matrices
- Analysis of a Classical Matrix Preconditioning Algorithm
- Matrix Preconditioning Techniques and Applications
- A preconditioning approach to the pagerank computation problem
This page was built for publication: Matrix algebras in optimal preconditioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5947456)