Robust low-rank data matrix approximations

We review some recent approaches to robust approximations of low-rank data matrices. We consider the problem of estimating a low-rank mean matrix when the data matrix is subject to measurement errors as well as gross outliers in some of its entries. The purpose of the paper is to make various algorithms accessible with an understanding of their abilities and limitations to perform robust low-rank matrix approximations in both low and high dimensional problems.     

A partial proximal point algorithm for nuclear norm regularized matrix least squares problems

We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semi-smoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.     

Diagonally compensated reduction and related preconditioning methods

When solving linear algebraic equations with large and sparse coefficient matrices, arising, for instance, from the discretization of partial differential equations, it is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme. Incomplete factorizations and sparse approximate inverses can provide efficient preconditioning methods but their existence and convergence theory is based mostly on M-matrices (H-matrices). In some application areas, however, the arising coefficient matrices are not H-matrices. This is the case, for instance, when higher-order finite element approximations are used, which is typical for structural mechanics problems. We show that modification of a symmetric, positive definite matrix by reduction of positive offdiagonal entries and diagonal compensation of them leads to an M-matrix. This diagonally compensated reduction can take place in the whole matrix or only at the current pivot block in a recursive incomplete factorization method. Applications for constructing preconditioning matrices for finite element matrices are described.     

A general approach to analyse preconditioners for two‐by‐two block matrices

Two‐by‐two block matrices arise in various applications, such as in domain decomposition methods or when solving boundary value problems discretised by finite elements from the separation of the node set of the mesh into ‘fine’ and ‘coarse’ nodes. Matrices with such a structure, in saddle point form arise also in mixed variable finite element methods and in constrained optimisation problems. A general algebraic approach to construct, analyse and control the accuracy of preconditioners for matrices in two‐by‐two block form is presented. This includes both symmetric and nonsymmetric matrices, as well as indefinite matrices. The action of the preconditioners can involve element‐by‐element approximations and/or geometric or algebraic multigrid/multilevel methods. Copyright © 2011 John Wiley & Sons, Ltd.     

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices.

Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both – systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed.

A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix.     

An efficient analyse phase for element problems

The analyse phase of a sparse direct solver for symmetrically structured linear systems of equations is used to determine the sparsity pattern of the matrix factor. This allows the subsequent numerical factorisation and solve phases to be executed efficiently. Many direct solvers require the system matrix to be in assembled form. For problems arising from finite element applications, assembling and then using the system matrix can be costly in terms of both time and memory. This paper describes and implements a variant of the work of Gilbert, Ng and Peyton for matrices in elemental form. The proposed variant works with an equivalent matrix that avoids explicitly assembling the system matrix and exploits supervariables. Numerical experiments using problems from practical applications are used to demonstrate the significant advantages of working directly with the elemental form. Copyright © 2012 John Wiley & Sons, Ltd.     

On a method for construction of successive approximations for investigation of multipoint boundary-value problems

We suggest a new scheme of successive approximations. This scheme allows one to study the problem of existence and approximate construction of solutions of nonlinear ordinary differential equations with multipoint linear boundary conditions. This method enables one to study problems both with singular and nonsingular matrices in boundary conditions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 9, pp. 1243–1253, September, 1995.     

Magnus integrators for solving linear-quadratic differential games

We consider Magnus integrators to solve linear-quadratic N$N$-player differential games. These problems require to solve, backward in time, non-autonomous matrix Riccati differential equations which are coupled with the linear differential equations for the dynamic state of the game, to be integrated forward in time. We analyze different Magnus integrators which can provide either analytical or numerical approximations to the equations. They can be considered as time-averaging methods and frequently are used as exponential integrators. We show that they preserve some of the most relevant qualitative properties of the solution for the matrix Riccati differential equations as well as for the remaining equations. The analytical approximations allow us to study the problem in terms of the parameters involved. Some numerical examples are also considered which show that exponential methods are, in general, superior to standard methods.     

On the existence of mosaic-skeleton approximations for discrete analogues of integral operators

Exterior three-dimensional Dirichlet problems for the Laplace and Helmholtz equations are considered. By applying methods of potential theory, they are reduced to equivalent Fredholm boundary integral equations of the first kind, for which discrete analogues, i.e., systems of linear algebraic equations (SLAEs) are constructed. The existence of mosaic-skeleton approximations for the matrices of the indicated systems is proved. These approximations make it possible to reduce the computational complexity of an iterative solution of the SLAEs. Numerical experiments estimating the capabilities of the proposed approach are described.     

Algebraic multilevel iteration method for Stieltjes matrices

The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

Methods of the secant type for systems of equations with symmetric jacobian matrix

Symmetric methods (SS methods) of the secant type are proposed for systems of equations with symmetric Jacobian matrix. The SSI and SS2 methods generate sequences of symmetric matrices J and H which approximate the Jacobian matrix and inverse one, respectively. Rank-two quasi-Newton formulas for updating J and H are derived. The structure of the approximations J and H is better than the structure of the corresponding approximations in the traditional secant method because the SS methods take into account symmetry of the Jacobian matrix. Furthermore, the new methods retain the main properties of the traditional secant method, namely, J and H are consistent approximations to the Jacobian matrix; the SS methods converge superlinearly; the sequential (n + 1)-point SS methods have the R-order at least equal to the positive root of t_n+1-1=0.     

On the application of mosaic-skeleton approximations of matrices for the acceleration of computations in the vortex method for the three-dimensional Euler equations

We study the possibility of using fast matrix multiplication methods for the approximation of the velocity field when solving the system of differential equations describing the vorticity transport in an ideal incompressible fluid in Lagrangian coordinates. We suggest a numerical scheme that permits effectively using the fast matrix multiplication (the method of mosaic-skeleton approximations). We show that the functions used for the computation of the velocity field and moving grids appearing in the solution of the problem permit one to use the above-mentioned method. We prove the convergence of the resulting numerical solution to the exact solution with regard of the error contributed by the use of the algorithm for approximate fast multiplication of matrices by vectors.     

Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

Finite-difference methods for solving loaded parabolic equations

Loaded partial differential equations are solved numerically. For illustrative purposes, a boundary value problem for a parabolic equation with various point loads is considered. By applying difference approximations, the problems are reduced to systems of algebraic equations of special structure, which are solved using a parametric representation involving solutions of auxiliary linear systems with tridiagonal matrices. Numerical results are presented and analyzed.     

On element-by-element Schur complement approximations

We discuss a methodology to construct sparse approximations of Schur complements of two-by-two block matrices arising in Finite Element discretizations of partial differential equations. Earlier results from [2] are extended to more general symmetric positive definite matrices of two-by-two block form. The applicability of the method for general symmetric and nonsymmetric matrices is analysed. The paper demonstrates the applicability of the presented method providing extensive numerical experiments.     

On sinc discretization and banded preconditioning for linear third‐order ordinary differential equations

Some draining or coating fluid‐flow problems and problems concerning the flow of thin films of viscous fluid with a free surface can be described by third‐order ordinary differential equations (ODEs). In this paper, we solve the boundary value problems of such equations by sinc discretization and prove that the discrete solutions converge to the true solutions of the ODEs exponentially. The discrete solution is determined by a linear system with the coefficient matrix being a combination of Toeplitz and diagonal matrices. The system can be effectively solved by Krylov subspace iteration methods, such as GMRES, preconditioned by banded matrices. We demonstrate that the eigenvalues of the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the linear system. Numerical examples are given to illustrate the effective performance of our method. Copyright © 2010 John Wiley & Sons, Ltd.     

The Chebyshev approximation of a rectangular matrix by matrices of smaller rank as the limit of lp-apprpoximation

In this paper we investigate a connection between l_p-approximation and the Chebyshev approximation of a rectangular matrix by matrices of smaller rank. We consider also the stationary points of problems (4) and (5) which are connected with these approximations.