The Implementation of a Jacobi-Type Method

We present both the implementation and some of its numericalresults of a Jacobi-type method for the triangularization ofarbitrary matrices. We also present some discussions concerningconvergence difficulties of a Jacobi-type method for computingeigenvalues of arbitrary matrices.     

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.     

Computing generalized inverses of a rational matrix and applications

In this paper we investigate symbolic implementation of two modifications of the Leverrier-Faddeev algorithm, which are applicable in computation of the Moore-Penrose and the Drazin inverse of rational matrices. We introduce an algorithm for computation of the Drazin inverse of rational matrices. This algorithm represents an extension of the papers [11] and [14]. and a continuation of the papers [15, 16]. The symbolic implementation of these algorithms in the package mathEmatica is developed. A few matrix equations are solved by means of the Drazin inverse and the Moore-Penrose inverse of rational matrices.     

Computing the nearest diagonally dominant matrix

We solve the problem of minimizing the distance from a given matrix to the set of symmetric and diagonally dominant matrices. First, we characterize the projection onto the cone of diagonally dominant matrices with positive diagonal, and then we apply Dykstra's alternating projection algorithm on this cone and on the subspace of symmetric matrices to obtain the solution. We discuss implementation details and present encouraging preliminary numerical results. Copyright © 1999 John Wiley & Sons, Ltd.     

Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

We describe an implementation of nonsymmetric interior-point methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones. We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interior-point solvers for semidefinite programming.     

Implementation of exponential Rosenbrock-type integrators

In this paper, we present a variable step size implementation of exponential Rosenbrock-type methods of orders 2, 3 and 4. These integrators require the evaluation of exponential and related functions of the Jacobian matrix. To this aim, the Real Leja Points Method is used. It is shown that the properties of this method combine well with the particular requirements of Rosenbrock-type integrators. We verify our implementation with some numerical experiments in MATLAB, where we solve semilinear parabolic PDEs in one and two space dimensions. We further present some numerical experiments in FORTRAN, where we compare our method with other methods from literature. We find a great potential of our method for non-normal matrices. Such matrices typically arise in parabolic problems with large advection in combination with moderate diffusion and mildly stiff reactions.     

Effective partitioning method for computing generalized inverses and their gradients

We extend the algorithm for computing {1}, {1, 3}, {1, 4} inverses and their gradients from [11] to the set of multiple-variable rational and polynomial matrices. An improvement of this extension, appropriate to sparse polynomial matrices with relatively small number of nonzero coefficient matrices as well as in the case when the nonzero coefficient matrices are sparse, is introduced. For that purpose, we exploit two effective structures form [6], which make use of only nonzero addends in polynomial matrices, and define their partial derivatives. Symbolic computational package MATHEMATICA is used in the implementation. Several randomly generated test matrices are tested and the CPU times required by two used effective structures are compared and discussed.     

On the computation of the rank of block bidiagonal Toeplitz matrices

In the present paper we study the computation of the rank of a block bidiagonal Toeplitz (BBT) sequence of matrices. We propose matrix-based, numerical and symbolical, updating and direct methods, computing the rank of BBT matrices and comparing them with classical procedures. The methods deploy the special form of the BBT sequence, significantly reducing the required flops and leading to fast and efficient algorithms. The numerical implementation of the algorithms computes the numerical rank in contrast with the symbolical implementation, which guarantees the computation of the exact rank of the matrix. The combination of numerical and symbolical operations suggests a new approach in software mathematical computations denoted as hybrid computations.     

A note on the <Emphasis Type="BoldItalic">O</Emphasis>(<Emphasis Type="BoldItalic">n</Emphasis>)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices

We propose a new O(n)-space implementation of the GKO-Cauchy algorithm for the solution of linear systems where the coefficient matrix is Cauchy-like. Moreover, this new algorithm makes a more efficient use of the processor cache memory; for matrices of size larger than n ≈ 500–1,000, it outperforms the customary GKO algorithm. We present an applicative case of Cauchy-like matrices with non-reconstructible main diagonal. In this special instance, the O(n) space algorithms can be adapted nicely to provide an efficient implementation of basic linear algebra operations in terms of the low displacement-rank generators.     

An Incomplete Cholesky Factorization for Dense Symmetric Positive Definite Matrices

In this paper, we study the use of an incomplete Cholesky factorization (ICF) as a preconditioner for solving dense symmetric positive definite linear systems. This method is suitable for situations where matrices cannot be explicitly stored but each column can be easily computed. Analysis and implementation of this preconditioner are discussed. We test the proposed ICF on randomly generated systems and large matrices from two practical applications: semidefinite programming and support vector machines. Numerical comparison with the diagonal preconditioner is also presented.     

On the Leverrier-Faddeev algorithm for computing the Moore-Penrose inverse

We present an improvement in the implementation of the Leverrier-Faddeev algorithm for symbolic computation of the Moore-Penrose inverse of one-variable polynomial matrices, introduced in Linear Algebra Appl. 252, 35–60 (1997). Complexity analysis of the original algorithm and its improvement is presented. Algorithm and its improvement are implemented and compared in the symbolic computational package MATHEMATICA. We compare CPU time required for computation of some test matrices by means of the original algorithm and its improvement.     

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.     

The block conjugate gradient algorithm and related methods

The development of the Lanczos algorithm for finding eigenvalues of large sparse symmetric matrices was followed by that of block forms of the algorithm. In this paper, similar extensions are carried out for a relative of the Lanczos method, the conjugate gradient algorithm. The resulting block algorithms are useful for simultaneously solving multiple linear systems or for solving a single linear system in which the matrix has several separated eigenvalues or is not easily accessed on a computer. We develop a block biconjugate gradient algorithm for general matrices, and develop block conjugate gradient, minimum residual, and minimum error algorithms for symmetric semidefinite matrices. Bounds on the rate of convergence of the block conjugate gradient algorithm are presented, and issues related to computational implementation are discussed. Variants of the block conjugate gradient algorithm applicable to symmetric indefinite matrices are also developed.     

Fast computation of Hermite normal forms of random integer matrices

This paper is about how to compute the Hermite normal form of a random integer matrix in practice. We propose significant improvements to the algorithm by Micciancio and Warinschi, and extend these techniques to the computation of the saturation of a matrix. We describe the fastest implementation for computing Hermite normal form for large matrices with large entries.     

Computing the matrix geometric mean: Riemannian versus Euclidean conditioning,implementation techniques,and a Riemannian BFGS method

This paper addresses the problem of computing the Riemannian center of mass of a collection of symmetric positive definite matrices. We show in detail that the condition number of the Riemannian Hessian of the underlying optimization problem is never very ill conditioned in practice, which explains why the Riemannian steepest descent approach has been observed to perform well. We also show theoretically and empirically that this property is not shared by the Euclidean Hessian. We then present a limited‐memory Riemannian BFGS method to handle this computational task. We also provide methods to produce efficient numerical representations of geometric objects that are required for Riemannian optimization methods on the manifold of symmetric positive definite matrices. Through empirical results and a computational complexity analysis, we demonstrate the robust behavior of the limited‐memory Riemannian BFGS method and the efficiency of our implementation when compared to state‐of‐the‐art algorithms.     

Circulant preconditioners for Toeplitz-block matrices

We propose two block preconditioners for Toeplitz-block matrices (i.e. each block is Toeplitz), intended to be used in conjunction with conjugate gradient methods. These preconditioners employ and extend existing circulant preconditioners for point Toeplitz matrices. The two preconditioners differ in whether the point circulant approximation is used once or twice, and also in the cost per step. We discuss efficient implementation of these two preconditioners, as well as some basic theoretical properties (such as preservation of symmetry and positive definiteness). We report results of numerical experiments, including an example from active noise control, to compare their performance.Research supported by SRI International and by the Army Research Office under contract DAAL03-91-G-0150 and by the Office of Naval Research under contract N00014-90-J-1695.     

Numerical experiments with ABS algorithms for linear systems on a parallel machine

Numerical results are obtained on sequential and parallel versions of ABS algorithms for linear systems for both full matrices andq-band matrices. The results using the sequential algorithm on full matrices indicate the superiority of a particular implementation of the symmetric algorithm. The condensed form of the algorithm is well suited for implementation in a parallel environment, and results obtained on the IBM 4381 system favor a synchronous implementation over the asynchronous one. Results are obtained from sequential implementations of theLU, Cholesky, and symmetric algorithms of the ABS class forq-band matrices able to reduce memory storage. A simple parallelization of do-loops for calculating components gives interesting performances.This work has been developed in the framework of a collaboration between IBM-ECSEC, Rome, Italy, and the Department of Mathematics of the University of Bergamo, Bergamo, Italy.The author is grateful to Prof. J. Abaffy (University of Economics, Budapest), Prof. L. Dixon (Hatfield Polytechnic), and Prof. E. Spedicato (Department of Mathematics, University of Bergamo) for useful suggestions.     

On the characteristic polynomial,eigenvectors and determinant of heptadiagonal matrices

In this paper, the characteristic polynomial of general heptadiagonal matrices is derived as well as eigenvectors associated to a prescribed eigenvalue. A symbolic algorithm to compute the determinant of heptadiagonal matrices is also presented allowing a suite implementation through computational software programs.     

On computing of block ILU preconditioner for block tridiagonal systems

We present the recurrence formulas for computing the approximate inverse factors of tridiagonal and pentadiagonal matrices using bordering technique. Resulting algorithms are used to approximate the inverse of pivot blocks needed for constructing block ILU preconditioners for solving the block tridiagonal linear systems, arising from discretization of partial differential equations. Resulting preconditioners are suitable for parallel implementation. Comparison with other methods are also included.