The preconditioned inverse iteration for hierarchical matrices

The preconditioned inverse iteration is an efficient method to compute the smallest eigenpair of a symmetric positive definite matrix M. Here we use this method to find the smallest eigenvalues of a hierarchical matrix. The storage complexity of the data‐sparse ‐matrices is almost linear. We use ‐arithmetic to precondition with an approximate inverse of M or an approximate Cholesky decomposition of M. In general, ‐arithmetic is of linear‐polylogarithmic complexity, so the computation of one eigenvalue is cheap. We extend the ideas to the computation of inner eigenvalues by computing an invariant subspace S of (M ? μI)² by subspace preconditioned inverse iteration. The eigenvalues of the generalized matrix Rayleigh quotient μ_M(S) are the desired inner eigenvalues of M. The idea of using (M ? μI)² instead of M is known as the folded spectrum method. As we rely on the positive definiteness of the shifted matrix, we cannot simply apply shifted inverse iteration therefor. Numerical results substantiate the convergence properties and show that the computation of the eigenvalues is superior to existing algorithms for non‐sparse matrices.Copyright © 2012 John Wiley & Sons, Ltd.     

Homotopic residual correction processes

We present and analyze homotopic (continuation) residual correction algorithms for the computation of matrix inverses. For complex indefinite Hermitian input matrices, our homotopic methods substantially accelerate the known nonhomotopic algorithms. Unlike the nonhomotopic case our algorithms require no pre-estimation of the smallest singular value of an input matrix. Furthermore, we guarantee rapid convergence to the inverses of well-conditioned structured matrices even where no good initial approximation is available. In particular we yield the inverse of a well-conditioned matrix with a structure of Toeplitz/Hankel type in flops. For a large class of input matrices, our methods can be extended to computing numerically the generalized inverses. Our numerical experiments confirm the validity of our analysis and the efficiency of the presented algorithms for well-conditioned input matrices and furnished us with the proper values of the parameters that define our algorithms.

     

A Quadratically Convergent Algorithm for Structured Low-Rank Approximation

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix \(M\), the goal is to compute a matrix \(M'\) of given rank \(r\) in a linear or affine subspace \(E\) of matrices (usually encoding a specific structure) such that the Frobenius distance \(\left\| M-M' \right\| \) is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank \(r\) and the linear/affine subspace \(E\). We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank \(r\) matrices in \(E\). To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank matrix completion (coordinate spaces) and denoising procedures (Hankel matrices).     

Tight representations of semilattices and inverse semigroups

By a Boolean inverse semigroup we mean an inverse semigroup whose semilattice of idempotents is a Boolean algebra. We study representations of a given inverse semigroup in a Boolean inverse semigroup which are tight in a certain well defined technical sense. These representations are supposed to preserve as much as possible any trace of Booleanness present in the semilattice of idempotents of  . After observing that the Vagner–Preston representation is not tight, we exhibit a canonical tight representation for any inverse semigroup with zero, called the regular tight representation. We then tackle the question as to whether this representation is faithful, but it turns out that the answer is often negative. The lack of faithfulness is however completely understood as long as we restrict to continuous inverse semigroups, a class generalizing the E ^*-unitaries. Partially supported by CNPq.     

On generalized inverse transversals

Let S be a regular semigroup, S° an inverse subsemigroup of S.S° is called a generalized inverse transversal of S, if V（x）∩S°≠Ф. In this paper, some properties of this kind of semigroups are discussed. In particular, a construction theorem is obtained which contains some recent results in the literature as its special cases.     

A Note on Ultrametric Matrices

It is proved in this paper that special generalized ultrametric and special matrices are, in a sense, extremal matrices in the boundary of the set of generalized ultrametric and matrices, respectively. Moreover, we present a new class of inverse M-matrices which generalizes the class of matrices.     

Complex powers of degenerate differential operators connected with the Klein-Gordon-Fock operator

We develop a theory of complex powers of the generalized Klein-Gordon-Fock operator

$m^2 - \square - i\lambda \frac{{\partial ^2 }}{{\partial x_1^2 }},\lambda > 0.$

. The negative powers of this operator are realized as potential-type integrals with nonstandard metrics, while positive powers inverse to negative ones are realized as approximative inverse operators.

     

Some results on the Drazin inverse of anti-triangular matrices

Abstract

The representations for the Drazin inverse of anti-triangular matrices are obtained under some conditions. Applying these representations, we give a necessary condition for a class of block matrices to have signed Drazin inverse.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.     

Stability estimates for the inverse boundary value problem by partial Cauchy data

We study the inverse conductivity problem with partial data in dimension n ≥ 3. We derive stability estimates for this inverse problem if the conductivity has regularity for 0 < σ < 1. Copyright © 2014 John Wiley & Sons, Ltd.