Search

The paper considers a Jacobi method for solving the generalized eigenvalue problem Ax = λBx, where A and B are complex Hermitian matrices and B is positive definite. The method is a proper generalization of the standard Jacobi method for the Hermitian matrix A to the matrix pair (A,B). The paper derives the method and proves its global convergence under the large class of generalized serial pivot strategies. If both matrices are positive definite, it can be implemented as a one-sided method. It then solves the initial problem as the generalized singular value problem. Its main application is to serve as a kernel algorithm in a block Jacobi method for the same problem with large matrices A and B. The block Jacobi methods are methods of choice on contemporary CPU and GPU computing architectures. The proposed algorithm is very efficient on pairs of almost diagonal matrices, and diagonalization of such matrices is the main task of the kernel algorithm. The numerical tests indicate the high relative accuracy of the method on certain pairs of positive definite matrices. [ABSTRACT FROM AUTHOR]

The concept of the core problem in total least squares (TLS) problems with single right-hand side introduced in [C. C. Paige and Z. Strakoš, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 861-875] separates necessary and sufficient information for solving the problem from redundancies and irrelevant information contained in the data. It is based on orthogonal transformations such that the resulting problem decomposes into two independent parts. One of the parts has nonzero right-hand side and minimal dimensions and it always has the unique TLS solution. The other part has trivial (zero) right-hand side and maximal dimensions. Assuming exact arithmetic, the core problem can be obtained by the Golub-Kahan bidiagonalization. Extension of the core concept to the multiple right-hand sides case AX ≈ B in [I. Hnětynková, M. Plešinger, and Z. Strakoš, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 917-931], which is highly nontrivial, is based on application of the singular value decomposition. In this paper we prove that the band generalization of the Golub--Kahan bidiagonalization proposed in this context by Björck also yields the core problem. We introduce generalized Jacobi matrices and investigate their properties. They prove useful in further analysis of the core problem concept. This paper assumes exact arithmetic. [ABSTRACT FROM AUTHOR]

The problem discussed in this paper is the symmetric best low multilinear rank approximation of third-order symmetric tensors. We propose an algorithm based on Jacobi rotations, for which symmetry is preserved at each iteration. Two numerical examples are provided indicating the need for such algorithms. An important part of the paper consists of proving that our algorithm converges to stationary points of the objective function. This can be considered an advantage of the proposed algorithm over existing symmetry-preserving algorithms in the literature. [ABSTRACT FROM AUTHOR]

Higher order tensor inversion is possible for even order. This is due to the fact that a tensor group endowed with the contracted product is isomorphic to the general linear group of degree n. With these isomorphic group structures, we derive a tensor SVD which we have shown to be equivalent to well-known canonical polyadic decomposition and multilinear SVD provided that some constraints are satisfied. Moreover, within this group structure framework, multilinear systems are derived and solved for problems of high-dimensional PDEs and large discrete quantum models. We also address multilinear systems which do not fit the framework in the least-squares sense. These are cases when there is an odd number of modes or when each mode has distinct dimension. Numerically we solve multilinear systems using iterative techniques, namely, biconjugate gradient and Jacobi methods. [ABSTRACT FROM AUTHOR]

We study inexact Rayleigh quotient iteration (IRQI) for computing a simple interior eigen-pair of the generalized eigenvalue problem Av = λBv, providing new insights into a special type of preconditioners with "tuning" for the efficient iterative solution of the shifted linear systems that arise in this algorithm. We first give a new convergence analysis of IRQI, showing that locally cubic and quadratic convergence can be achieved for Hermitian and non-Hermitian problems, respectively, if the shifted linear systems air solved by a generic Krylov subspace method with a tuned preconditioner to a reasonably small fixed tolerance. We then refine the study by Freitag and Spence [Linear Algebra Appl., 428 (2008), pp. 2049-2000] on the equivalence the inner solves of IRQI and single-vector Jacobi--Davidson method where a full orthogonalization method with a tuned preconditioner is used as the inner solver. We also provide some new perspectives on the tuning strategy, showing that tuning is essentially needed only in the first inner iteration in the non-Hermitian case. Based on this observation, we propose a flexible GMRES algorithm with a special configuration in the first inner step, and show that this method is as efficient as GMRES with the tuned preconditioner. [ABSTRACT FROM AUTHOR]

This paper introduces a globally convergent block (column- and row-) cyclic Jacobi method for diagonalization of Hermitian matrices and for computation of the singular value decomposition of general matrices. It is shown that a block rotation (a generalization of the Jacobi 2 × 2 rotation) can be computed and implemented in a particular way to guarantee global convergence. The proof includes the convergence of the eigenspaces in the general case of multiple eigenvalues. This solves a long standing open problem of convergence of block cyclic Jacobi methods. [ABSTRACT FROM AUTHOR]

The Jacobi-Davidson method is an eigenvalue solver which uses an inner-outer scheme. In the outer iteration one tries to approximate an eigenpair while in the inner iteration a linear system has to be solved, often iteratively, with the ultimate goal to make progress for the outer loop. In this paper we prove a relation between the residual norm of the inner linear system and the residual norm of the eigenvalue problem. We show that the latter may be estimated inexpensively during the inner iterations. On this basis, we propose a stopping strategy for the inner iterations to maximally exploit the strengths of the method. These results extend previous results obtained for the special case of Hermitian eigenproblems with the conjugate gradient or the symmetric QMR method as inner solver. The present analysis applies to both standard and generalized eigenproblems, does not require symmetry, and is compatible with most iterative methods for the inner systems. It can also be extended to other types of inner-outer eigenvalue solvers, such as inexact inverse iteration or inexact Rayleigh quotient iteration. The effectiveness of our approach is illustrated by a few numerical experiments, including the comparison of a standard Jacobi-Davidson code with the same code enhanced by our stopping strategy. [ABSTRACT FROM AUTHOR]

This paper proves that the two-sided Jacobi method computes the eigenvalues of the indefinite symmetric matrix to high relative accuracy, provided that the initial matrix is scaled diagonally dominant. It proves sharp eigenvalue perturbation bounds coming from a single Jacobi step and from the whole sweep defined by the serial pivot strategies. [ABSTRACT FROM AUTHOR]

Suppose A = (aijk) ϵ ℝn×n×n is a three-way array or third-order tensor. Many of the powerful tools of linear algebra such as the singular value decomposition (SVD) do not, unfortunately, extend in a straightforward way to tensors of order three or higher. In the twodimensional case, the SVD is particularly illuminating, since it reduces a matrix to diagonal form. Although it is not possible in general to diagonalize a tensor (i.e., aijk = 0 unless i = j = k), our goal is to "condense" a tensor in fewer nonzero entries using orthogonal transformations. We propose an algorithm for tensors of the form A ϵ ℝn×n×n that is an extension of the Jacobi SVD algorithm for matrices. The resulting tensor decomposition reduces A to a form such that the quantity Σn i=1 a2 iii or Σn i=1 aiii is maximized. [ABSTRACT FROM AUTHOR]

This work deals with the generalized eigenvalue problem for nonsquare matrix pencils A - ⋋B such that matrices A,B ϵ MC (m×n) show a given structure. More precisely, we assume they result from removing the first row of some matrix G ϵ MC ((m+1) , n) in the case of A, and its last row in the case of B. This structured generalized eigenvalue problem can be found in signal processing methods and in the numerical computation of the greatest common divisor (GCD) of polynomials. Traditional methods for solving the problem (A - ⋋B) v = 0 do not yield valid solutions when the data are not exact, as is often the case in real applications. In this work we adopt a minimal perturbation approach. Taking into account the structure of the matrices involved, we develop a simple algorithm for the computation of the generalized eigenvalues. [ABSTRACT FROM AUTHOR]

We present explicit formulas for the distributions of the extreme eigenvalues of the β-Jacobi random matrix ensemble in terms of the hypergeometric function of a matrix argument. For β = 1, 2, 4, these formulas specialize to the well-known real, complex, and quaternion Jacobi ensembles, respectively. [ABSTRACT FROM AUTHOR]

This paper proves the global convergence of a block-oriented, quasi-cyclic Jacobi method for symmetric matrices. The result applies to the new fast one-sided Jacobi method, proposed by Drmač and Veselić, for computing the singular value decomposition. There is no restriction on the matrix block-partition which defines the pivot strategy. [ABSTRACT FROM AUTHOR]

In this paper we study numerical stability of the parallel Jacobi method for computing the singular values and singular subspaces of an invertible upper triangular matrix that is obtained from QR decomposition with column pivoting. We show that in this case the parallel Jacobi method locates singular values and singular subspaces to full machine accuracy. [ABSTRACT FROM AUTHOR]

We are interested in computing the minimal positive solution of a nonsymmetric algebraic Riccati equation arising in transport theory. We show that this computation can be done via computing only the minimal positive solution of a vector equation, which is derived from the special form of solutions of the Riccati equation. A simple iterative method is presented for solving the vector equation. The simple iteration is much more efficient than the Gauss-Jacobi method presented by Juang in [Linear Algebra Appl., 230 (1995), pp. 89-100] for the Riccati equation. The symmetric case and bounds of the minimal positive solution are also considered. Numerical experiments are given. [ABSTRACT FROM AUTHOR]

We propose a minimax scaling procedure for second order polynomial matrices that aims to minimize the backward errors incurred in solving a particular linearized generalized eigenvalue problem. We give numerical examples to illustrate that it can significantly improve the backward errors of the computed eigenvalue-eigenvector pairs. [ABSTRACT FROM AUTHOR]

A generalization of the cyclic Jacobi algorithm is proposed that works in an arbitrary compact Lie algebra. This allows, in particular, a unified treatment of Jacobi algorithms on different classes of matrices, e.g., skew-symmetric or skew-Hermitian Hamiltonian matrices. Wildberger has established global, linear convergence of the algorithm for the classical Jacobi method on compact Lie algebras. Here we prove local quadratic convergence for general cyclic Jacobi schemes. [ABSTRACT FROM AUTHOR]

Multiplicative backward stability results are presented for two algorithms which compute the singular value decomposition of dense matrices. These algorithms are the classical onesided Jacobi algorithm, with a stringent stopping criterion, and an algorithm which uses one-sided Jacobi to compute high accurate singular value decompositions of matrices given as rank-revealing factorizations. When multiplicative backward errors are small, the multiplicative perturbation theory for the singular value decomposition developed in the last decade can be applied to get high accuracy bounds on the errors of the computed singular values and vectors. [ABSTRACT FROM AUTHOR]

We discuss structure-preserving Jacobi-like algorithms for the solution of the indefinite generalized Hermitian eigenvalue problem. We discuss a method based on the solution of Hermitian 4 × 4 subproblems which generalizes the Jacobi-like method of Bunse-Gerstner and Faßbender for Hamiltonian matrices. Furthermore, we discuss structure-preserving Jacobi-like methods based on the solution of non-Hermitian 2 × 2 subproblems. For these methods a local convergence proof is given. Numerical test results for the comparison of the proposed methods are presented. [ABSTRACT FROM AUTHOR]

We present a new numerical iterative method for computing selected eigenpairs of a right definite two-parameter eigenvalue problem. The method works even without good initial approximations and is able to tackle large problems that are too expensive for existing methods. The new method is similar to the Jacobi-Davidson method for the eigenvalue problem. In each step, we first compute Ritz pairs of a small projected right definite two-parameter eigenvalue problem and then expand the search spaces using approximate solutions of appropriate correction equations. We present two alternatives for the correction equations, introduce a selection technique that makes it possible to compute more than one eigenpair, and give some numerical results. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for floating-point computation of the quotient singular value decomposition of an arbitrary matrix pair (A, B) ∈ Rm×n× Rp×n. In the case of full column rank A, the new algorithm computes all finite quotient singular values with high relative accuracy if min{κ2(AD), D diagonal} is moderate and if an accurate rank revealing LU factorization of B is possible. Numerical experiments show that in such a case the new algorithm computes the quotient singular values of all pairs (AD, D1BD2) with nearly the same accuracy, where D, D1, D2 are arbitrary diagonal nonsingular matrices. [ABSTRACT FROM AUTHOR]

We show that three well-known perturbation bounds for matrix eigenvalues imply relative bounds: the Bauer­Fike and Hoffman­Wielandt theorems for diagonalizable matrices, and Weyl's theorem for Hermitian matrices. As a consequence, relative perturbation bounds are not necessarily stronger than absolute bounds, and the conditioning of an eigenvalue in the relative sense is the same as in the absolute sense. We also show that eigenvalues of normal matrices are no more sensitive to perturbations than eigenvalues of Hermitian positive-definite matrices. The relative error bounds are invariant under congruence transformations, such as grading and scaling.

Let H and H + ΔH be positive definite matrices. It was shown by Barlow and Demmel and Demmel and Veselić that if one takes a componentwise approach one can prove much stronger bounds on λi(H)/λi(H + ΔH) and the components of the eigenvectors of H and H + ΔH than by using the standard normwise perturbation theory. Here a unified approach is presented that improves on the results of Barlow, Demmel, and Veselić. It is also shown that the growth factor associated with the error bound on the components of the eigenvectors computed by Jacobi's method grows linearly (rather than exponentially) with the number of Jacobi iterations required for convergence. [ABSTRACT FROM AUTHOR]