Unified approach to unconstrained minimization via basic matrix factorizations

Important classes of algorithms for unconstrained minimization, when applied to a quadratic with Hessian A, may be regarded as alternative ways to effect certain basic matrix factorizations of or with respect to A. This approach enables a unified presentation of many existing algorithms and suggests some new algorithms. Two basic underlying factorizations are of particular interest—tridiagonalization coupled with Cholesky factorization and the Gram-Schmidt or QR factorization.     

An analysis of the HR algorithm for computing the eigenvalues of a matrix

The HR algorithm, a method of computing the eigenvalues of a matrix, is presented. It is based on the fact that almost every complex square matrix A can be decomposed into a product A = HR of a so-called pseudo-Hermitian matrix H and an upper triangular matrix R. This algorithm is easily seen to be a generalization of the well-known QR algorithm. It is shown how it is related to the power method and inverse iteration, and for special matrices the connection between the LR and HR algorithms is indicated.     

A fast algorithm for subspace state-space system identification via exploitation of the displacement structure

Two recent approaches (Van Overschee, De Moor, N4SID, Automatica 30 (1) (1994) 75; Verhaegen, Int. J. Control 58(3) (1993) 555) in subspace identification problems require the computation of the R factor of the QR factorization of a block-Hankel matrix H, which, in general has a huge number of rows. Since the data are perturbed by noise, the involved matrix H is, in general, full rank. It is well known that, from a theoretical point of view, the R factor of the QR factorization of H is equivalent to the Cholesky factor of the correlation matrix H^TH, apart from a multiplication by a sign matrix. In Sima (Proceedings Second NICONET Workshop, Paris-Versailles, December 3, 1999, p. 75), a fast Cholesky factorization of the correlation matrix, exploiting the block-Hankel structure of H, is described. In this paper we consider a fast algorithm to compute the R factor based on the generalized Schur algorithm. The proposed algorithm allows to handle the rank–deficient case.     

Assignment and scheduling in parallel matrix factorization

We consider the problem of factoring a dense n×n matrix on a network consisting of P MIMD processors, with no shared memory, when the network is smaller than the number of elements in the matrix (P<n²). The specific example analyzed is a computational network that arises in computing the LU, QR, or Cholesky factorizations. We prove that if the nodes of the network are evenly distributed among processors and if computations are scheduled by a round-robin or a least-recently-executed scheduling algorithm, then optimal order of speedup is achieved. However, such speedup is not necessarily achieved for other scheduling algorithms or if the computation for the nodes is inappropriately split across processors, and we give examples of these phenomena. Lower bounds on execution time for the algorithm are established for two important node-assignment strategies.     

Bases for kernel-based spaces

Since it is well-known (De Marchi and Schaback (2001) [4]) that standard bases of kernel translates are badly conditioned while the interpolation itself is not unstable in function space, this paper surveys the choices of other bases. All data-dependent bases turn out to be defined via a factorization of the kernel matrix defined by these data, and a discussion of various matrix factorizations (e.g. Cholesky, QR, SVD) provides a variety of different bases with different properties. Special attention is given to duality, stability, orthogonality, adaptivity, and computational efficiency. The “Newton” basis arising from a pivoted Cholesky factorization turns out to be stable and computationally cheap while being orthonormal in the “native” Hilbert space of the kernel. Efficient adaptive algorithms for calculating the Newton basis along the lines of orthogonal matching pursuit conclude the paper.     

Bases for kernel-based spaces

Since it is well-known (De Marchi and Schaback (2001) [4]) that standard bases of kernel translates are badly conditioned while the interpolation itself is not unstable in function space, this paper surveys the choices of other bases. All data-dependent bases turn out to be defined via a factorization of the kernel matrix defined by these data, and a discussion of various matrix factorizations (e.g. Cholesky, QR, SVD) provides a variety of different bases with different properties. Special attention is given to duality, stability, orthogonality, adaptivity, and computational efficiency. The “Newton” basis arising from a pivoted Cholesky factorization turns out to be stable and computationally cheap while being orthonormal in the “native” Hilbert space of the kernel. Efficient adaptive algorithms for calculating the Newton basis along the lines of orthogonal matching pursuit conclude the paper.     

A unitary Hessenberg QR-based algorithm via semiseparable matrices

In this paper, we present a novel method for solving the unitary Hessenberg eigenvalue problem. In the first phase, an algorithm is designed to transform the unitary matrix into a diagonal-plus-semiseparable form. Then we rely on our earlier adaptation of the QR algorithm to solve the dpss eigenvalue problem in a fast and robust way. Exploiting the structure of the problem enables us to yield a quadratic time using a linear memory space. Nonetheless the algorithm remains robust and converges as fast as the customary QR algorithm. Numerical experiments confirm the effectiveness and the robustness of our approach.     

Computing Row and Column Counts for Sparse QR and LU Factorization

We present algorithms to determine the number of nonzeros in each row and column of the factors of a sparse matrix, for both the QR factorization and the LU factorization with partial pivoting. The algorithms use only the nonzero structure of the input matrix, and run in time nearly linear in the number of nonzeros in that matrix. They may be used to set up data structures or schedule parallel operations in advance of the numerical factorization.The row and column counts we compute are upper bounds on the actual counts. If the input matrix is strong Hall and there is no coincidental numerical cancellation, the counts are exact for QR factorization and are the tightest bounds possible for LU factorization.These algorithms are based on our earlier work on computing row and column counts for sparse Cholesky factorization, plus an efficient method to compute the column elimination tree of a sparse matrix without explicitly forming the product of the matrix and its transpose.This revised version was published online in October 2005 with corrections to the Cover Date.     

Odd prime values of the Ramanujan tau function

We study the odd prime values of the Ramanujan tau function, which form a thin set of large primes. To this end, we define LR(p,n):=τ(p ^n?1) and we show that the odd prime values are of the form LR(p,q) where p,q are odd primes. Then we exhibit arithmetical properties and congruences of the LR numbers using more general results on Lucas sequences. Finally, we propose estimations and discuss numerical results on pairs (p,q) for which LR(p,q) is prime.     

Componentwise perturbation bounds for some matrix decompositions

Componentwise perturbation bounds for the Cholesky,LDL ^H ,QR andLU decompositions are derived. The bounds improve known results of the same type and reveal the structural characteristics of the perturbations.This subject was supported by the Institute of Information Processing of the University of Umeå and the Swedish Natural Science Research Council.     

An algorithm for the symmetric generalized eigenvalue problem

A new method is presented for the solution of the matrix eigenvalue problem Ax=λBx, where A and B are real symmetric square matrices and B is positive semidefinite. It reduces A and B to diagonal form by congruence transformations that preserve the symmetry of the problem. This method is closely related to the QR algorithm for real symmetric matrices.     

On Shape-Preserving Additions of Fuzzy Intervals

We prove an open problem suggested by Mesiar (1997, Fuzzy Sets and Systems86, 73-78) concerning continuous t-norm-based additions preserving the LR-fuzzy intervals.     

A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix

A fast method for computing all the eigenvalues of a Hamiltonian matrix M is given. The method relies on orthogonal symplectic similarity transformations which preserve structure and have desirable numerical properties. The algorithm requires about one-fourth the number of floating-point operations and one-half the space of the standard QR algorithm. The computed eigenvalues are shown to be the exact eigenvalues of a matrix M + E where ∥E∥ depends on the square root of the machine precision. The accuracy of a computed eigenvalue depends on both its condition and its magnitude, larger eigenvalues typically being more accurate.     

On neighbouring matrices with quadratic elementary divisors

Summary Algorithms are presented which compute theQR factorization of an order-n Toeplitz matrix inO(n ²) operations. The first algorithm computes onlyR explicitly, and the second computes bothQ andR. The algorithms are derived from a well-known procedure for performing the rank-1 update ofQR factors, using the shift-invariance property of the Toeplitz matrix. The algorithms can be used to solve the Toeplitz least-squares problem, and can be modified to solve Toeplitz systems inO(n) space.     

Ein quadratisch konvergentes Verfahren zur Eigenwertbestimmung bei unsymmetrischen Matrizen I

Summary J. C. F. Francis proposes for the determination of eigenvalues of an arbitrary matrix theQR-transformation which is a unitary analogue of theLR-transformation. In this process the current approximation matrix is always factorized into a unitary and a triangular matrix and the 2 factors are multiplied together in reverse order; this yields the next approximant. The present paper shows how this process may be extended to a process which transforms a given matrix with quadratic convergence orthogonally toWintner-Murnaghan's normal form. The process is formulated in the real domain.     

The differential form spectrum of quaternionic hyperbolic spaces

By using harmonic analysis and representation theory, we determine explicitly the L² spectrum of the Hodge-de Rham Laplacian acting on quaternionic hyperbolic spaces and we show that the unique possible discrete eigenvalue and the lowest continuous eigenvalue can both be realized by some subspace of hypereffective differential forms. Similar results are obtained also for the Bochner Laplacian.     

Positive top Lyapunov exponent via invariant cones: Single trajectories

We establish criteria for the positivity of the top Lyapunov exponent of a nonautonomous dynamics in terms of invariant cone families, both for maps and flows. The families of cones are associated with quadratic forms of type (k,p−k)$(k,p-k)$ with k arbitrary. Our work can be seen as a counterpart of results in the context of ergodic theory, where the positivity of the top Lyapunov exponent is obtained for almost all trajectories although saying nothing about each specific trajectory.     

Polynomial least squares fitting in the Bernstein basis

The problem of polynomial least squares fitting in which the usual monomial basis is replaced by the Bernstein basis is considered. The coefficient matrix of the overdetermined system to be solved in the least squares sense is then a rectangular Bernstein-Vandermonde matrix. In order to use the method based on the QR decomposition of A, the first stage consists of computing the bidiagonal decomposition of the coefficient matrix A. Starting from that bidiagonal decomposition, an algorithm for obtaining the QR decomposition of A is the applied. Finally, a triangular system is solved by using the bidiagonal decomposition of the R-factor of A. Some numerical experiments showing the behavior of this approach are included.     

Arithmetic differential equations on $$GL_n$$, II: arithmetic Lie–Cartan theory

Motivated by the search of a concept of linearity in the theory of arithmetic differential equations (Buium in Arithmetic differential equations. Math. surveys and monographs, vol 118. American Mathematical Society, Providence, 2005), we introduce here an arithmetic analogue of Lie algebras, of Chern connections, and of Maurer–Cartan connections. Our arithmetic analogues of Chern connections are certain remarkable lifts of Frobenius on the p-adic completion of \(GL_n\) which are uniquely determined by certain compatibilities with the “outer” involutions defined by symmetric (respectively, antisymmetric) matrices. The Christoffel symbols of our arithmetic Chern connections will involve a matrix analogue of the Legendre symbol. The analogues of Maurer–Cartan connections can then be viewed as families of “linear” flows attached to each of our Chern connections. We will also investigate the compatibility of lifts of Frobenius with the inner automorphisms of \(GL_n\); in particular, we will prove the existence and uniqueness of certain arithmetic analogues of “isospectral flows” on the space of matrices.     

Instability of the self-similar flow into a cavity

In this paper we have investigated the instability of the self-similar flow behind the boundary of a collapsing cavity. The similarity solutions for the flow into a cavity in a fluid obeying a gas lawp = K_ρ ^γ, K = constant and 7 ≥ γ > 1 has been solved by Hunter, who finds that for the same value of γ there are two self-similar flows, one with accelerating cavity boundary and other with constant velocity cavity boundary. We find here that the first of these two flows is unstable. We arrive at this result only by studying the propagation of disturbances in the neighbourhood of the singular point.