On the fast Lanczos method for computation of eigenvalues of Hankel matrices using multiprecision arithmetics

The use of the fast Fourier transform (FFT) accelerates Lanczos tridiagonalisation method for Hankel and Toeplitz matrices by reducing the complexity of matrix–vector multiplication. In multiprecision arithmetics, the FFT has overheads that make it less competitive compared with alternative methods when the accuracy is over 10000 decimal places. We studied two alternative Hankel matrix–vector multiplication methods based on multiprecision number decomposition and recursive Karatsuba‐like multiplication, respectively. The first method was uncompetitive because of huge precision losses, while the second turned out to be five to 14 times faster than FFT in the ranges of matrix sizes up to n = 8192 and working precision of b = 32768 bits we were interested in. We successfully applied our approach to eigenvalues calculations to studies of spectra of matrices that arise in research on Riemann zeta function. The recursive matrix–vector multiplication significantly outperformed both the FFT and the traditional multiplication in these studies. Copyright © 2016 John Wiley & Sons, Ltd.     

On Distinguished Solutions of Truncated Matricial Hamburger Moment Problems

We study two slightly different versions of the truncated matricial Hamburger moment problem. A central topic is the construction and investigation of distinguished solutions of both moment problems under consideration. These solutions turn out to be nonnegative Hermitian q × q Borel measures on the real axis which are concentrated on a finite number of points. These points and the corresponding masses will be explicitly described in terms of the given data. Furthermore, we investigate a particular class of sequences (s_j)^∞_{j = 0} of complex q × q matrices for which the corresponding infinite matricial Hamburger moment problem has a unique solution. Our approach is mainly algebraic. It is based on the use of particular matrix polynomials constructed from a nonnegative Hermitian block Hankel matrix. These matrix polynomials are immediate generalizations of the monic orthogonal matrix polynomials associated with a positive Hermitian block Hankel matrix. We generalize a classical theorem due to Kronecker on infinite Hankel matrices of finite rank to block Hankel matrices and discuss its consequences for the nonnegative Hermitian case.     

The DJL Conjecture for CP Matrices over Special Inclines

Drew, Johnson, and Loewy conjectured that for n ≥ 4, the CP-rank of every n × n completely positive real matrix is at most [n²/4]. While this conjecture has recently been disproved for completely positive real matrices, we show that this conjecture is true for n × n completely positive matrices over certain special types of inclines. In addition, we prove an incline version of Markham's theorems which gives sufficient conditions for completely positive matrices over special inclines to have triangular factorizations.     

Minimal condition number for positive definite Hankel matrices using semidefinite programming

We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24?n?30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n?24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.     

Factorization of a class of matrix‐functions with stable partial indices

A new effective method for factorization of a class of nonrational n × n matrix‐functions with stable partial indices is proposed. The method is a generalization of one recently proposed by the authors, which was valid for the canonical factorization only. The class of matrices being considered is motivated by their applicability to various problems. The properties and steps of the asymptotic procedure are discussed in detail. The efficiency of the procedure is highlighted by numerical results. Copyright © 2016 John Wiley & Sons, Ltd.     

Efficient generation of random nonsingular matrices

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n²), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n² + 3. (Over other finite fields we use n² + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.     

Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.     

The inverse problem of bisymmetric matrices with a submatrix constraint

An n×n real matrix A is called a bisymmetric matrix if A=A^T and A=S_nAS_n, where S_n is an n×n reverse unit matrix. This paper is mainly concerned with solving the following two problems: Problem I Given n×m real matrices X and B, and an r×r real symmetric matrix A₀, find an n×n bisymmetric matrix A such that where A([1: r]) is a r×r leading principal submatrix of the matrix A. Problem II Given an n×n real matrix A^*, find an n×n matrix  in S_E such that where ∥·∥ is Frobenius norm, and S_E is the solution set of Problem I. The necessary and sufficient conditions for the existence of and the expressions for the general solutions of Problem I are given. The explicit solution, a numerical algorithm and a numerical example to Problem II are provided. Copyright © 2003 John Wiley & Sons, Ltd.     

On two particular cases of solving the normal Hankel problem

The normal Hankel problem is one of characterizing all the complex matrices that are normal and Hankel at the same time. The matrix classes that can contain normal Hankel matrices admit a parameterization by real 2 × 2 matrices with determinant one. Here, the normal Hankel problem is solved in the case where the characteristic matrix of a given class is an order two Jordan block for the eigenvalue 1 or ?1.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

The solution of the equation AX + BX ⋆ = 0

We give a complete solution of the matrix equation AX?+?BX ^??=?0, where A, B?∈?? ^m×n are two given matrices, X?∈?? ^n×n is an unknown matrix, and ? denotes the transpose or the conjugate transpose. We provide a closed formula for the dimension of the solution space of the equation in terms of the Kronecker canonical form of the matrix pencil A?+?λB, and we also provide an expression for the solution X in terms of this canonical form, together with two invertible matrices leading A?+?λB to the canonical form by strict equivalence.     

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.     

A twisted factorization method for symmetric SVD of a complex symmetric tridiagonal matrix

This paper presents an O(n²) method based on the twisted factorization for computing the Takagi vectors of an n‐by‐n complex symmetric tridiagonal matrix with known singular values. Since the singular values can be obtained in O(n²) flops, the total cost of symmetric singular value decomposition or the Takagi factorization is O(n²) flops. An analysis shows the accuracy and orthogonality of Takagi vectors. Also, techniques for a practical implementation of our method are proposed. Our preliminary numerical experiments have verified our analysis and demonstrated that the twisted factorization method is much more efficient than the implicit QR method, divide‐and‐conquer method and Matlab singular value decomposition subroutine with comparable accuracy. Copyright © 2009 John Wiley & Sons, Ltd.     

On construction of involutory MDS matrices from Vandermonde Matrices in GF(2 q )

Due to their remarkable application in many branches of applied mathematics such as combinatorics, coding theory, and cryptography, Vandermonde matrices have received a great amount of attention. Maximum distance separable (MDS) codes introduce MDS matrices which not only have applications in coding theory but also are of great importance in the design of block ciphers. Lacan and Fimes introduce a method for the construction of an MDS matrix from two Vandermonde matrices in the finite field. In this paper, we first suggest a method that makes an involutory MDS matrix from the Vandermonde matrices. Then we propose another method for the construction of 2 ⁿ × 2 ⁿ Hadamard MDS matrices in the finite field GF(2 ^q ). In addition to introducing this method, we present a direct method for the inversion of a special class of 2 ⁿ ?× 2 ⁿ Vandermonde matrices.     

Tournament matrices and their generalizations,I.

If M is any complex matrix with rank (M + M ^* + I) = 1, we show that any eigenvalue of M that is not geometrically simple has 1/2 for its real part. This generalizes a recent finding of de Caen and Hoffman: the rank of any n × n tournament matrix is at least n ? 1. We extend several spectral properties of tournament matrices to this and related types of matrices. For example, we characterize the singular real matrices M with 0 diagonal for which rank (M + M^T + I) = 1 and we characterize the vectors that can be in the kernels of such matrices. We show that singular, irreducible n × n tournament matrices exist if and only n? {2,3,4,5} and exhibit many infinite families of such matrices. Connections with signed digraphs are explored and several open problems are presented.     

The Constrained Solutions of Two Matrix Equations

We study the symmetric positive semidefinite solution of the matrix equation AX ₁ A ^T + BX ₂ B ^T = C, where A is a given real m×n matrix, B is a given real m×p matrix, and C is a given real m×m matric, with m, n, p positive integers; and the bisymmetric positive semidefinite solution of the matrix equation D ^T XD = C, where D is a given real n×m matrix, C is a given real m×m matrix, with m, n positive integers. By making use of the generalized singular value decomposition, we derive general analytic formulae, and present necessary and sufficient conditions for guaranteeing the existence of these solutions. Received December 17, 1999, Revised January 10, 2001, Accepted March 5, 2001     

Reduced Vertex Set Result for Interval Semidefinite Optimization Problems

In this paper we propose a reduced vertex result for the robust solution of uncertain semidefinite optimization problems subject to interval uncertainty. If the number of decision variables is m and the size of the coefficient matrices in the linear matrix inequality constraints is n×n, a direct vertex approach would require satisfaction of 2 ^{n(m+1)(n+1)/2} vertex constraints: a huge number, even for small values of n and m. The conditions derived here are instead based on the introduction of m slack variables and a subset of vertex coefficient matrices of cardinality 2 ⁿ⁻¹, thus reducing the problem to a practically manageable size, at least for small n. A similar size reduction is also obtained for a class of problems with affinely dependent interval uncertainty. This work is supported by MIUR under the FIRB project “Learning, Randomization and Guaranteed Predictive Inference for Complex Uncertain Systems,” and by CNR RSTL funds.     

Distributions of eigenvalues and inertias of some block Hermitian matrices consisting of orthogonal projectors

A complex square matrix A is called an orthogonal projector if A ²?=?A?=?A*, where A* is the conjugate transpose of A. In this article, we first give some formulas for calculating the distributions of real eigenvalues of a linear combination of two orthogonal projectors. Then, we establish various expansion formulas for calculating the inertias, ranks and signatures of some 2?×?2 and 3?×?3, as well as k?×?k block Hermitian matrices consisting of two orthogonal projectors. Many applications of the formulas are presented in characterizing interval distributions of numbers of eigenvalues, and nonsingularity of these block Hermitian matrices. In addition, necessary and sufficient conditions are given for various equalities and inequalities of these block Hermitian matrices to hold.     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.