Approximate iterations for structured matrices

Important matrix-valued functions f (A) are, e.g., the inverse A ⁻¹, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of A ⁻¹ and . This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig) and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of the Department of Mathematical Sciences of the Russian Academy of Sciences.     

Structured total least norm and approximate GCDs of inexact polynomials

The determination of an approximate greatest common divisor (GCD) of two inexact polynomials f=f(y)$f=f(y)$ and g=g(y)$g=g(y)$ arises in several applications, including signal processing and control. This approximate GCD can be obtained by computing a structured low rank approximation S^*(f,g)$S^{*}(f,g)$ of the Sylvester resultant matrix S(f,g)$S(f,g)$. In this paper, the method of structured total least norm (STLN) is used to compute a low rank approximation of S(f,g)$S(f,g)$, and it is shown that important issues that have a considerable effect on the approximate GCD have not been considered. For example, the established works only yield one matrix S^*(f,g)$S^{*}(f,g)$, and therefore one approximate GCD, but it is shown in this paper that a family of structured low rank approximations can be computed, each member of which yields a different approximate GCD. Examples that illustrate the importance of these and other issues are presented.     

Backward errors for eigenproblem of two kinds of structured matrices

In this paper, we consider backward errors in the eigenproblem of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices. By making use of the properties of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices, we derive explicit formulae for the backward errors of approximate eigenpairs.     

On the modification of an eigenvalue problem that preserves an eigenspace

Eigenvalue problems arise in many application areas ranging from computational fluid dynamics to information retrieval. In these fields we are often interested in only a few eigenvalues and corresponding eigenvectors of a sparse matrix. In this paper, we comment on the modifications of the eigenvalue problem that can simplify the computation of those eigenpairs. These transformations allow us to avoid difficulties associated with non-Hermitian eigenvalue problems, such as the lack of reliable non-Hermitian eigenvalue solvers, by mapping them into generalized Hermitian eigenvalue problems. Also, they allow us to expose and explore parallelism. They require knowledge of a selected eigenvalue and preserve its eigenspace. The positive definiteness of the Hermitian part is inherited by the matrices in the generalized Hermitian eigenvalue problem. The position of the selected eigenspace in the ordering of the eigenvalues is also preserved under certain conditions. The effect of using approximate eigenvalues in the transformation is analyzed and numerical experiments are presented.     

Continuation of Singular Value Decompositions

In this work we consider computing a smooth path for a (block) singular value decomposition of a full rank matrix valued function. We give new theoretical results and then introduce and implement several algorithms to compute a smooth path. We illustrate performance of the algorithms with a few numerical examples.This work was supported in part under NSF Grant DMS-0139895, and INDAM-GNCS and MIUR Rome-Italy.     

Eigenvalue computation for unitary rank structured matrices

In this paper we describe how to compute the eigenvalues of a unitary rank structured matrix in two steps. First we perform a reduction of the given matrix into Hessenberg form, next we compute the eigenvalues of this resulting Hessenberg matrix via an implicit QR-algorithm. Along the way, we explain how the knowledge of a certain ‘shift’ correction term to the structure can be used to speed up the QR-algorithm for unitary Hessenberg matrices, and how this observation was implicitly used in a paper due to William B. Gragg. We also treat an analogue of this observation in the Hermitian tridiagonal case.     

On the convergence rate of the conjugate gradients in presence of rounding errors

Summary We investigate here rounding error effects on the convergence rate of the conjugate gradients. More precisely, we analyse on both theoretical and experimental basis how finite precision arithmetic affects known bounds on iteration numbers when the spectrum of the system matrix presents small or large isolated eigenvalues.The present work was supported by the Programme d'impulsion en Technologie l'Information, financed by Belgian State, under contract No. IT/IF/14Supported by the Fonds National de la Recherche Scientifique, Chargé de recherches     

A method for approximation of the exponential map in semidirect product of matrix Lie groups and some applications

In this paper we explore the computation of the matrix exponential in a manner that is consistent with Lie group structure. Our point of departure is the decomposition of Lie algebra as the semidirect product of two Lie subspaces and an application of the Baker-Campbell-Hausdorff formula. Our results extend the results in Iserles and Zanna (2005) [2], Zanna and Munthe-Kaas(2001/02) [4] to a range of Lie groups: the Lie group of all solid motions in Euclidean space, the Lorentz Lie group of all solid motions in Minkowski space and the group of all invertible (upper) triangular matrices. In our method, the matrix exponential group can be computed by a less computational cost and is more accurate than the current methods. In addition, by this method the approximated matrix exponential belongs to the corresponding Lie group.     

Block tridiagonal reduction of perturbed normal and rank structured matrices

It is well known that if a matrix A∈C^n×n$A\in {\mathbb{C}}^{n\times n}$ solves the matrix equation f(A,A^H)=0$f(A,A^H)=0$, where f(x,y)$f(x,y)$ is a linear bivariate polynomial, then A is normal; A   and A^H$A^H$ can be simultaneously reduced in a finite number of operations to tridiagonal form by a unitary congruence and, moreover, the spectrum of A is located on a straight line in the complex plane. In this paper we present some generalizations of these properties for almost normal matrices which satisfy certain quadratic matrix equations arising in the study of structured eigenvalue problems for perturbed Hermitian and unitary matrices.     

Modified block-approximate factorization strategies

Summary Two variants of modified incomplete block-matrix factorization with additive correction are proposed for the iterative solution of large linear systems of equations. Both rigorous theoretical support and numerical evidence are given displaying their efficiency when applied to discrete second order partial differential equations (PDEs), even in the case of quasi-singular problems.Research supported by the A.B.O.S. (A.G.C.D.) under project 11, within the co-operation between Belgium and Zaire     

A framework for polynomial preconditioners based on fast transforms I: Theory

Optimal and superoptimal approximations of a complex square matrix by polynomials in a normal basis matrix are considered. If the unitary transform associated with the eigenvectors of the basis matrix is computable using a fast algorithm, the approximations may be utilized for constructing preconditioners. Theorems describing how the parameters of the approximations could be efficiently computed are given, and for special cases earlier results by other authors are recovered. Also, optimal and superoptimal approximations for block matrices are determined, and the same type of theorems as for the point case are proved. This research was supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the U.S. National Science Foundation under grant ASC-8958544.     

On computing PageRank via lumping the Google matrix

Computing Google’s PageRank via lumping the Google matrix was recently analyzed in [I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl. 29 (2007) 1281–1296]. It was shown that all of the dangling nodes can be lumped into a single node and the PageRank could be obtained by applying the power method to the reduced matrix. Furthermore, the stochastic reduced matrix had the same nonzero eigenvalues as the full Google matrix and the power method applied to the reduced matrix had the same convergence rate as that of the power method applied to the full matrix. Therefore, a large amount of operations could be saved for computing the full PageRank vector.     

The alternate-block-factorization procedure for systems of partial differential equations

The alternate-block-factorization (ABF) method is a procedure for partially decoupling systems of elliptic partial differential equations by means of a carefully chosen change of variables. By decoupling we mean that the ABF strategy attempts to reduce intra-equation coupling in the system rather than intra-grid coupling for a single elliptic equation in the system. This has the effect of speeding convergence of commonly used iteration schemes, which use the solution of a sequence of linear elliptic PDEs as their main computational step. Algebraically, the change of variables is equivalent to a postconditioning of the original system. The results of using ABF postconditioning on some problems arising from semiconductor device simulation are discussed.The work of R. E. Bank was supported in part by the Office of Naval Research under contract N00014-82K-0197. The work of T. F. Chan was supported in part by the National Science Foundation under grant NSF-DMS87-14612 and by the Army Research Office under contract DAAL03-88-K-0085.     

Solving Hankel matrix approximation problem using semidefinite programming

Positive semidefinite Hankel matrices arise in many important applications. Some of their properties may be lost due to rounding or truncation errors incurred during evaluation. The problem is to find the nearest matrix to a given matrix to retrieve these properties. The problem is converted into a semidefinite programming problem as well as a problem comprising a semidefined program and second-order cone problem. The duality and optimality conditions are obtained and the primal–dual algorithm is outlined. Explicit expressions for a diagonal preconditioned and crossover criteria have been presented. Computational results are presented. A possibility for further improvement is indicated.     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

On the convergence of splittings for semidefinite linear systems

Recently, Lee et al. [Young-ju Lee, Jinbiao Wu, Jinchao Xu, Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006) 634-641] introduce new criteria for the semi-convergence of general iterative methods for semidefinite linear systems based on matrix splitting. The new conditions generalize the classical notion of P-regularity introduced by Keller [H.B. Keller, On the solution of singular and semidefinite linear systems by iterations, SIAM J. Numer. Anal. 2 (1965) 281-290]. In view of their results, we consider here stipulations on a splitting A=M-N, which lead to fixed point systems such that, the iterative scheme converges to a weighted Moore-Penrose solution to the system Ax=b. Our results extend the result of Lee et al. to a more general case and we also show that it requires less restrictions on the splittings than Keller’s P-regularity condition to ensure the convergence of iterative scheme.     

Convergence of a generalized MSSOR method for augmented systems

Recently, Wu et al. [S.-L. Wu, T.-Z. Huang, X.-L. Zhao, A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math. 228 (1) (2009) 424-433] introduced a modified SSOR (MSSOR) method for augmented systems. In this paper, we establish a generalized MSSOR (GMSSOR) method for solving the large sparse augmented systems of linear equations, which is the extension of the MSSOR method. Furthermore, the convergence of the GMSSOR method for augmented systems is analyzed and numerical experiments are carried out, which show that the GMSSOR method with appropriate parameters has a faster convergence rate than the MSSOR method with optimal parameters.