Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996     

Tangential frequency filtering decompositions for symmetric matrices

Summary. The tangential frequency filtering decomposition (TFFD) is introduced. The convergence theory of an iterative scheme based on the TFFD for symmetric matrices is the focus of this paper. The existence of the TFFD and the convergence of the induced iterative algorithm is shown for symmetric and positive definite matrices. Convergence rates independent of the number of unknowns are proven for a smaller class of matrices. Using this framework, the convergence independent of the number of unknowns is shown for Wittum's frequency filtering decomposition. Some characteristic properties of the TFFD are illustrated and results of several numerical experiments are presented. Received April 1, 1996 / Revised version July 4, 1996     

UTV Tools: Matlab templates for rank-revealing UTV decompositions

We describe a Matlab 5.2 package for computing and modifying certain rank-revealing decompositions that have found widespread use in signal processing and other applications. The package focuses on algorithms for URV and ULV decompositions, collectively known as UTV decompositions. We include algorithms for the ULLV decomposition, which generalizes the ULV decomposition to a pair of matrices. For completeness a few algorithms for computation of the RRQR decomposition are also included. The software in this package can be used as is, or can be considered as templates for specialized implementations on signal processors and similar dedicated hardware platforms. This revised version was published online in June 2006 with corrections to the Cover Date.     

Block-Arnoldi and Davidson methods for unsymmetric large eigenvalue problems

Summary We present two methods for computing the leading eigenpairs of large sparse unsymmetric matrices. Namely the block-Arnoldi method and an adaptation of the Davidson method to unsymmetric matrices. We give some theoretical results concerning the convergence and discuss implementation aspects of the two methods. Finally some results of numerical tests on a variety of matrices, in which we compare these two methods are reported.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

New GMRES(k)-Type Algorithms with Explicit Restarts and the Analysis of Their Convergence Properties Based on Matrix Relations in QR Form

The paper considers the problem of constructing a basic iterative scheme for solving systems of linear algebraic equations with unsymmetric and indefinite coefficient matrices. A new GMRES-type algorithm with explicit restarts is suggested. When restarting, this algorithm takes into account the spectral/singular data transferred using orthogonal matrix relations in the so-called QR form, which arise when performing inner iterations of Arnoldi type. The main idea of the algorithm developed is to organize inner iterations and the filtering of directions before restarting in such a way that, from one restart to another, matrix relations effectively accumulate information concerning the current approximate solution and, simultaneously, spectral/singular data, which allow the algorithm to converge with a rate comparable with that of the GMRES algorithm without restarts. Convergence theory is provided for the case of nonsingular, unsymmetric, and indefinite matrices. A bound for the rate of decrease of the residual in the course of inner Arnoldi-type iterations is obtained. This bound depends on the spectral/singular characterization of the subspace spanned by the directions retained upon filtering and is used in developing efficient filtering procedures. Numerical results are provided. Bibliography: 9 titles.     

Real linear Kronecker product operations

The Kronecker product in the real linear matrix analytic setting is studied. More versatile operations are proposed. Such generalizations are of interest for the same reasons the standard Kronecker product is. To give an example, new preconditioning ideas are suggested. In connection with this, several formulae for the inverse are devised. Orthogonal decompositions of real-entried matrices are derived through introducing new Kronecker product SVDs. Matrix equations are given to illustrate how the Kronecker product structures introduced can arise.     

IBLU decompositions based on Padé approximants

In this paper, we introduce a new class of frequency‐filtering IBLU decompositions that use continued‐fraction approximation for the diagonal blocks. This technique allows us to construct efficient frequency‐filtering preconditioners for discretizations of elliptic partial differential equations on domains with non‐trivial geometries. We prove theoretically for a class of model problems that the application of the proposed preconditioners leads to a convergence rate of up to 1?O(h^1/4) of the CG iteration. Copyright © 2008 John Wiley & Sons, Ltd.     

Positive definiteness in the numerical solution of Riccati differential equations

Summary. In this work we address the issue of integrating symmetric Riccati and Lyapunov matrix differential equations. In many cases -- typical in applications -- the solutions are positive definite matrices. Our goal is to study when and how this property is maintained for a numerically computed solution. There are two classes of solution methods: direct and indirect algorithms. The first class consists of the schemes resulting from direct discretization of the equations. The second class consists of algorithms which recover the solution by exploiting some special formulae that these solutions are known to satisfy. We show first that using a direct algorithm -- a one-step scheme or a strictly stable multistep scheme (explicit or implicit) -- limits the order of the numerical method to one if we want to guarantee that the computed solution stays positive definite. Then we show two ways to obtain positive definite higher order approximations by using indirect algorithms. The first is to apply a symplectic integrator to an associated Hamiltonian system. The other uses stepwise linearization. Received April 21, 1993     

Preconditioned conjugate gradient methods for large-scale fluid flow applications

The simulation of large-scale fluid flow applications often requires the efficient solution of extremely large nonsymmetric linear and nonlinear sparse systems of equations arising from the discretization of systems of partial differential equations. While preconditioned conjugate gradient methods work well for symmetric, positive-definite matrices, other methods are necessary to treat large, nonsymmetric matrices. The applications may also involve highly localized phenomena which can be addressed via local and adaptive grid refinement techniques. These local refinement methods usually cause non-standard grid connections which destroy the bandedness of the matrices and the associated ease of solution and vectorization of the algorithms. The use of preconditioned conjugate gradient or conjugate-gradient-like iterative methods in large-scale reservoir simulation applications is briefly surveyed. Then, some block preconditioning methods for adaptive grid refinement via domain decomposition techniques are presented and compared. These techniques are being used efficiently in existing large-scale simulation codes.     

Stability analysis and fast algorithms for triangularization of Toeplitz matrices

Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in . Received April 30, 1995 / Revised version received February 12, 1996     

Fast inversion algorithms for diagonal plus semiseparable matrices

Here are considered matrices represented as a sum of diagonal and semiseparable ones. These matrices belong to the class of structured matrices which arises in numerous applications. FastO(N) algorithms for their inversion were developed before under additional restrictions which are a source of instability. Our aim is to eliminate these restrictions and to develop reliable and stable numerical algorithms. In this paper we obtain such algorithms with the only requirement that the considered matrix is invertible and its determinant is not close to zero. The case of semiseparable matrices of order one was considered in detail in an earlier paper of the authors.     

The QRPS algorithm: A generalization of the QR algorithm for the singular values decomposition of rectangular matrices

A generalization of the QR algorithm proposed by Francis [2] for square matrices is introduced for the singular values decomposition of arbitrary rectangular matrices. Geometrically the algorithm means the subsequent orthogonalization of the image of orthonormal bases produced in the course of the iteration. Our purpose is to show how to get a series of lower triangular matrices by alternate orthogonal-upper triangular decompositions in different dimensions and to prove the convergence of this series.     

Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations

Conjugate gradient type methods are discussed for unsymmetric and inconsistent system of equations. For unsymmetric problems, besides conjugate gradient methods based on the normal equations, we also present a (modified) minimal residual (least square) method, which converges for systems with matrices that have a positive definite symmetric part. For inconsistent problems, for completeness we discuss briefly various (well-known) versions of the conjugate gradient method. Preconditioning and rate of convergence are also discussed.     

A periodic Krylov-Schur algorithm for large matrix products

Stewart's recently introduced Krylov-Schur algorithm is a modification of the implicitly restarted Arnoldi algorithm which employs reordered Schur decompositions to perform restarts and deflations in a numerically reliable manner. This paper describes a variant of the Krylov-Schur algorithm suitable for addressing eigenvalue problems associated with products of large and sparse matrices. It performs restarts and deflations via reordered periodic Schur decompositions and, by taking the product structure into account, it is capable of achieving qualitatively better approximations to eigenvalues of small magnitude. Supported by DFG Research Center Matheon, Mathematics for key technologies, in Berlin.     

Fast algorithms for Toeplitz and Hankel matrices

The paper gives a self-contained survey of fast algorithms for solving linear systems of equations with Toeplitz or Hankel coefficient matrices. It is written in the style of a textbook. Algorithms of Levinson-type and Schur-type are discussed. Their connections with triangular factorizations, Padè recursions and Lanczos methods are demonstrated. In the case in which the matrices possess additional symmetry properties, split algorithms are designed and their relations to butterfly factorizations are developed.     

Parameterized inverse singular value problem for anti-bisymmetric matrices

In this paper, the singular value decompositions of anti-symmetric matrices and anti-bisymmetric matrices are presented, and a class of parameterized inverse singular value problem for anti-bisymmetric matrices is solved. Numerical examples which confirm our theory are presented.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

Fast inversion of Chebyshev--Vandermonde matrices

Summary. This paper contains two fast algorithms for inversion of Chebyshev--Vandermonde matrices of the first and second kind. They are based on special representations of the Bezoutians of Chebyshev polynomials of both kinds. The paper also contains the results of numerical experiments which show that the algorithms proposed here are not only much faster, but also more stable than other algorithms available. It is also efficient to use the above two algorithms for solving Chebyshev--Vandermode systems of equations with preprocessing. Received January 23, 1993/Revised version received May 21, 1993