A robust AINV‐type method for constructing sparse approximate inverse preconditioners in factored form

This paper suggests a new method, called AINV‐A, for constructing sparse approximate inverse preconditioners for positive‐definite matrices, which can be regarded as a modification of the AINV method proposed by Benzi and Túma. Numerical results on SPD test matrices coming from different applications demonstrate the robustness of the AINV‐A method and its superiority to the original AINV approach. Copyright © 2001 John Wiley & Sons, Ltd.     

On eigenvalue distribution of constraint‐preconditioned symmetric saddle point matrices

This paper is devoted to the analysis of the eigenvalue distribution of two classes of block preconditioners for the generalized saddle point problem. Most of the bounds developed improve those appeared in previously published works. Numerical results onto a realistic test problem give evidence of the effectiveness of the estimates on the spectrum of preconditioned matrices. Copyright © 2011 John Wiley & Sons, Ltd.     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

On the inertia of the block H‐matrices

The problem of determining matrix inertia is very important in many applications, for example, in stability analysis of dynamical systems. In the (point‐wise) H‐matrix case, it was proven that the diagonal entries solely reveal this information. This paper generalises these results to the block H‐matrix cases for 1, 2, and matrix norms. The usefulness of the block approach is illustrated on 3 relevant numerical examples, arising in engineering.     

On commuting varieties of upper triangular matrices

It is known that the variety of the pairs of n×n commuting upper triangular matrices is not a complete intersection for infinitely many values of n; we show that there exists m such that this happens if and only if n>m. We also show that m<18 and that m could be found by determining the dimension of the variety of the pairs of commuting strictly upper triangular matrices. Then, we define an embedding of any commuting variety into a grassmannian of subspaces of codimension 2.     

Wilkinson's inertia‐revealing factorization and its application to sparse matrices

We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.     

Multicolor low‐rank preconditioner for general sparse linear systems

This article presents a multilevel parallel preconditioning technique for solving general large sparse linear systems of equations. Subdomain coloring is invoked to reorder the coefficient matrix by multicoloring the adjacency graph of the subdomains, resulting in a two‐level block diagonal structure. A full binary tree structure $\mathrm{??}$ is then built to facilitate the construction of the preconditioner. A key property that is exploited is the observation that the difference between the inverse of the original matrix and that of its block diagonal approximation is often well approximated by a low‐rank matrix. This property and the block diagonal structure of the reordered matrix lead to a multicolor low‐rank (MCLR) preconditioner. The construction procedure of the MCLR preconditioner follows a bottom‐up traversal of the tree $\mathrm{??}$. All irregular matrix computations, such as ILU factorizations and related triangular solves, are restricted to leaf nodes where these operations can be performed independently. Computations in nonleaf nodes only involve easy‐to‐optimize dense matrix operations. In order to further reduce the number of iteration of the Preconditioned Krylov subspace procedure, we combine MCLR with a few classical block‐relaxation techniques. Numerical experiments on various test problems are proposed to illustrate the robustness and efficiency of the proposed approach for solving large sparse symmetric and nonsymmetric linear systems.     

On preconditioners for the Laplace double‐layer in 2D

The discretization of the double‐layer potential integral equation for the interior Dirichlet–Laplace problem in a domain with smooth boundary results in a linear system that has a bounded condition number. Thus, the number of iterations required for the convergence of a Krylov method is, asymptotically, independent of the discretization size N. Using the fast multipole method to accelerate the matrix–vector products, we obtain an optimal solver. In practice, however, when the geometry is complicated, the number of Krylov iterations can be quite large—to the extend that necessitates the use of preconditioning. We summarize the different methodologies that have appeared in the literature (single‐grid, multigrid, approximate sparse inverses), and we propose a new class of preconditioners based on a fast multipole method‐based spatial decomposition of the double‐layer operator. We present an experimental study in which we compare the different approaches, and we discuss the merits and shortcomings of our approach. Our method can be easily extended to other second‐kind integral equations with non‐oscillatory kernels in two and three dimensions. Copyright © 2014 John Wiley & Sons, Ltd.     

Maps preserving square-zero matrices on the algebra consisting of all upper triangular matrices

Let F be a field, T _n (F) (respectively, N _n (F)) the matrix algebra consisting of all n × n upper triangular matrices (respectively, strictly upper triangular matrices) over F. A ∈ T _n (F) is said to be square zero if A ² = 0. In this article, we firstly characterize non-singular linear maps on N _n (F) preserving square-zero matrices in both directions, then by using it we determine non-singular linear maps on T _n (F) preserving square-zero matrices in both directions.     

Comment on ‘Preconditioning of matrices partitioned in 2 Œ 2 block form: Eigenvalue estimates and Schwarz DD for mixed FEM’ by Owe Axelsson,Radim Blaheta

In this note, we discuss the inverse representations of regularized saddle point matrices and point out that some conclusions given by Axelsson and Blaheta in [Numerical Linear Algebra with Applications, 2010,17:787–810 ] are not true.Copyright © 2011 John Wiley & Sons, Ltd.     

Blended kernel approximation in the ℋ︁‐matrix techniques

Several types of ??‐matrices were shown to provide a data‐sparse approximation of non‐local (integral) operators in FEM and BEM applications. The general construction is applied to the operators with asymptotically smooth kernel function provided that the Galerkin ansatz space has a hierarchical structure. The new class of ??‐matrices is based on the so‐called blended FE and polynomial approximations of the kernel function and leads to matrix blocks with a tensor‐product of block‐Toeplitz (block‐circulant) and rank‐k matrices. This requires the translation (rotation) invariance of the kernel combined with the corresponding tensor‐product grids. The approach allows for the fast evaluation of volume/boundary integral operators with possibly non‐smooth kernels defined on canonical domains/manifolds in the FEM/BEM applications. (Here and in the following, we call domains canonical if they are obtained by translation or rotation of one of their parts, e.g. parallelepiped, cylinder, sphere, etc.) In particular, we provide the error and complexity analysis for blended expansions to the Helmholtz kernel. Copyright © 2002 John Wiley & Sons, Ltd.     

A nearly optimal preconditioner for the Navier–Stokes equations

We present a preconditioner for the linearized Navier–Stokes equations which is based on the combination of a fast transform approximation of an advection diffusion problem together with the recently introduced ‘BFBT^T’ preconditioner of Elman (SIAM Journal of Scientific Computing, 1999; 20 :1299–1316). The resulting preconditioner when combined with an appropriate Krylov subspace iteration method yields the solution in a number of iterations which appears to be independent of the Reynolds number provided a mesh Péclet number restriction holds, and depends only mildly on the mesh size. The preconditioner is particularly appropriate for problems involving a primary flow direction. Copyright © 2001 John Wiley & Sons, Ltd.     

On the Drazin inverse of block matrices and generalized Schur complement

In this paper, we give an additive result for the Drazin inverse with its applications, we obtain representations for the Drazin inverse of a 2 × 2 complex block matrix having generalized Schur complement S=D-CA^DB equal to zero or nonsingular. Several situations are analyzed and recent results are generalized [R.E. Hartwig, X. Li, Y. Wei, Representations for the Drazin inverse of a 2×2 block matrix, SIAM J. Matrix Anal. Appl. 27 (3) (2006) 757-771].     

On some classes of structured matrices with algebraic trigonometric eigenvalues

Diagonal plus semiseparable matrices are constructed, the eigenvalues of which are algebraic numbers expressed by simple closed trigonometric formulas.     

Optimal solvers for linear systems with fractional powers of sparse SPD matrices

In this paper, we consider efficient algorithms for solving the algebraic equation , 0<α<1, where is a properly scaled symmetric and positive definite matrix obtained from finite difference or finite element approximations of second‐order elliptic problems in , d=1,2,3. This solution is then written as with with β positive integer. The approximate solution method we propose and study is based on the best uniform rational approximation of the function t^β−α for 0<t≤1 and on the assumption that one has at hand an efficient method (e.g., multigrid, multilevel, or other fast algorithms) for solving equations such as , c≥0. The provided numerical experiments confirm the efficiency of the proposed algorithms.