Two-weight Hilbert transform and Lipschitz property of Jacobi matrices associated to hyperbolic polynomials

We are going to prove a Lipschitz property of Jacobi matrices built by orthogonalizing polynomials with respect to measures in the orbit of classical Perron-Frobenius-Ruelle operators associated to hyperbolic polynomial dynamics. This Lipschitz estimate will not depend on the dimension of the Jacobi matrix. It is obtained using some sufficient conditions for two-weight boundedness of the Hilbert transform. It has been proved in [F. Peherstorfer, A. Volberg, P. Yuditskii, Limit periodic Jacobi matrices with prescribed p-adic hull and a singular continuous spectrum, Math. Res. Lett. 13 (2-3) (2006) 215-230] for all polynomials with sufficiently big hyperbolicity and in the most symmetric case t=0 that the Lipschitz estimate becomes exponentially better when the dimension of the Jacobi matrix grows. This allows us to get for such polynomials the solution of a problem of Bellissard, in other words, to prove the limit periodicity of the limit Jacobi matrix. We suggest a scheme how to approach Bellissard's problem for all hyperbolic dynamics by uniting the methods of the present paper and those of [F. Peherstorfer, A. Volberg, P. Yuditskii, Limit periodic Jacobi matrices with prescribed p-adic hull and a singular continuous spectrum, Math. Res. Lett. 13 (2-3) (2006) 215-230]. On the other hand, the nearness of Jacobi matrices under consideration in operator norm implies a certain nearness of their canonical spectral measures. One can notice that this last claim just gives us the classical commutative Perron-Frobenius-Ruelle theorem (it is concerned exactly with the nearness of such measures). In particular, in many situations we can see that the classical Perron-Frobenius-Ruelle theorem is a corollary of a certain non-commutative observation concerning the quantitative nearness of pertinent Jacobi matrices in operator norm.     

Three-level parallel J-Jacobi algorithms for Hermitian matrices

The paper describes several efficient parallel implementations of the one-sided hyperbolic Jacobi-type algorithm for computing eigenvalues and eigenvectors of Hermitian matrices. By appropriate blocking of the algorithms an almost ideal load balancing between all available processors/cores is obtained. A similar blocking technique can be used to exploit local cache memory of each processor to further speed up the process. Due to diversity of modern computer architectures, each of the algorithms described here may be the method of choice for a particular hardware and a given matrix size. All proposed block algorithms compute the eigenvalues with relative accuracy similar to the original non-blocked Jacobi algorithm.     

On computing quadrature-based bounds for the A-norm of the error in conjugate gradients

In their original paper, Golub and Meurant (BIT 37:687–705, 1997) suggest to compute bounds for the A-norm of the error in the conjugate gradient (CG) method using Gauss, Gauss-Radau and Gauss-Lobatto quadratures. The quadratures are computed using the (1,1)-entry of the inverse of the corresponding Jacobi matrix (or its rank-one or rank-two modifications). The resulting algorithm called CGQL computes explicitly the entries of the Jacobi matrix and its modifications from the CG coefficients. In this paper, we use the fact that CG computes the Cholesky decomposition of the Jacobi matrix which is given implicitly. For Gauss-Radau and Gauss-Lobatto quadratures, instead of computing the entries of the modified Jacobi matrices, we directly compute the entries of the Cholesky decompositions of the (modified) Jacobi matrices. This leads to simpler formulas in comparison to those used in CGQL.     

Computing the Hessenberg matrix associated with a self-similar measure

We introduce in this paper a method to calculate the Hessenberg matrix of a sum of measures from the Hessenberg matrices of the component measures. Our method extends the spectral techniques used by G. Mantica to calculate the Jacobi matrix associated with a sum of measures from the Jacobi matrices of each of the measures.We apply this method to approximate the Hessenberg matrix associated with a self-similar measure and compare it with the result obtained by a former method for self-similar measures which uses a fixed point theorem for moment matrices. Results are given for a series of classical examples of self-similar measures.Finally, we also apply the method introduced in this paper to some examples of sums of (not self-similar) measures obtaining the exact value of the sections of the Hessenberg matrix.     

实规范矩阵的特征值问题

实对称矩阵的特征值问题,无论是低阶稠密矩阵的全部特征值问题,或高阶稀疏矩阵的部分特征值问题,都已有许多有效的计算方法,迄今最重要的一些成果已总结在[5]中。本文利用规范矩阵的一些重要性质将对于Hermite矩阵(特别是对弥矩阵)特征值问题的一些有效算法推广到规范矩阵的特征值问题,由于对复规范阵的推广是简单的,而且实际上常遇到的是实矩阵(这时常要求只用实运算),因此我们着重讨论实规范矩阵的特征值问题。     

Efficient diagonalization of oversized matrices on a distributed-memory multiprocessor

On parallel architectures, Jacobi methods for computing the singular value decomposition (SVD) and the symmetric eigenvalue decomposition (EVD) have been established as one of the most popular algorithms due to their excellent parallelism. Most of the Jacobi algorithms for distributed-memory architectures have been developed under the assumption that matrices can be distributed over the processors by square blocks of an even order or column blocks with an even number of columns. Obviously, there is a limit on the number of processors while we need to deal with problems of various sizes. We propose algorithms to diagonalize oversized matrices on a given distributed-memory multiprocessor with good load balancing and minimal message passing. Performances of the proposed algorithms vary greatly, depending on the relation between the problem size and the number of available processors. We give theoretical performance analyses which suggest the faster algorithm for a given problem size on a given distributed-memory multiprocessor. Finally, we present a new implementation for the convergence test of the algorithms on a distributed-memory multiprocessor and the implementation results of the algorithms on the NCUBE/seven hypercube architecture.This work was supported by National Science Foundation grant CCR-8813493. This work was partly done during the author's visit to the Mathematical Science Section, Engineering Physics and Mathematics Division, Oak Ridge National Laboratory, while participating in the Special Year on Numerical Linear Algebra, 1988, sponsored by the UTK Departments of Computer Science and Mathematics, and the ORNL Algebra sponsored by the UTK Departments of Computer Science and Mathematics, and the ORNL Mathematical Sciences Section, Engineering Physics and Mathematics Division.     

The computation of the square roots of circulant matrices

In the first part of this paper, we investigate the reduced forms of circulant matrices and quasi-skew circulant matrices. By using their properties we present two efficient algorithms to compute the square roots of circulant matrices and quasi-skew circulant matrices, respectively. Those methods are faster than the traditional algorithm which is based on the Schur decomposition. In the second part, we further consider circulant H-matrices with positive diagonal entries and develop two algorithms for computing their principal square roots. Those two algorithms have the common advantage that is they only need matrix-matrix multiplications in their iterative sequences, an operation which can be done very efficiently on modern high performance computers.     

The spectral measure of a Jacobi matrix in terms of the Fourier transform of the perturbation

We study the spectral properties of Jacobi matrices. By combining Killip's technique [12] with the technique of Killip and Simon [13] we obtain a result relating the properties of the elements of Jacobi matrices and the corresponding spectral measures. This theorem is a natural extension of a recent result of Laptev-Naboko-Safronov [17]. The author thanks Sergei Naboko for useful discussions and Barry Simon for pointing out the conjecture.     

Novel modifications of parallel Jacobi algorithms

We describe two main classes of one-sided trigonometric and hyperbolic Jacobi-type algorithms for computing eigenvalues and eigenvectors of Hermitian matrices. These types of algorithms exhibit significant advantages over many other eigenvalue algorithms. If the matrices permit, both types of algorithms compute the eigenvalues and eigenvectors with high relative accuracy. We present novel parallelization techniques for both trigonometric and hyperbolic classes of algorithms, as well as some new ideas on how pivoting in each cycle of the algorithm can improve the speed of the parallel one-sided algorithms. These parallelization approaches are applicable to both distributed-memory and shared-memory machines. The numerical testing performed indicates that the hyperbolic algorithms may be superior to the trigonometric ones, although, in theory, the latter seem more natural.     

Thin spectra and singular continuous spectral measures for limit-periodic Jacobi matrices

This paper investigates the spectral properties of Jacobi matrices with limit-periodic coefficients. We show that generically the spectrum is a Cantor set of zero Lebesgue measure, and the spectral measures are purely singular continuous. For a dense set of limit-periodic Jacobi matrices, we show that the spectrum is a Cantor set of zero lower box counting dimension while still retaining the singular continuity of the spectral type. We also show how results of this nature can be established by fixing the off-diagonal coefficients and varying only the diagonal coefficients, and, in a more restricted version, by fixing the diagonal coefficients to be zero and varying only the off-diagonal coefficients. We apply these results to produce examples of weighted Laplacians on the multidimensional integer lattice having purely singular continuous spectral type and zero-dimensional spectrum.     

Accurate computations of matrices with bidiagonal decomposition using methods for totally positive matrices

A class of sign‐symmetric P‐matrices including all nonsingular totally positive matrices and their inverses as well as tridiagonal nonsingular H‐matrices is presented and analyzed. These matrices present a bidiagonal decomposition that can be used to obtain algorithms to compute with high relative accuracy their singular values, eigenvalues, inverses, or their LDU factorization. Copyright © 2012 John Wiley & Sons, Ltd.     

Spectra of infinite graphs with tails

We compute explicitly (modulo solutions of certain algebraic equations) the spectra of infinite graphs obtained by attaching one or several infinite paths to some vertices of given finite graphs. The main result concerns a canonical form for the adjacency matrix of such infinite graphs, and the algorithm of its calculation. The argument relies upon the spectral theory of eventually free Jacobi matrices. We also study some other couplings of infinite graphs (stars and Bethe–Caley trees).     

EP matrices: computation of the Moore-Penrose inverse via factorizations

EP matrices are a wide class of matrices which, among other things, can be characterized through factorizations. In this paper we are using two factorization algorithms in order to compute and factorize the Moore-Penrose inverse of a singular EP matrix. For the implementation of the algorithms we make use of a Computer Algebra System such as Maple. The results given by the proposed algorithms are faster and more accurate than the built-in Maple function in both symbolic and numerical tests, using matrices of different dimensions.     

Restricting Hecke-Siegel operators to Jacobi modular forms

We compute the action of Hecke operators on Jacobi forms of “Siegel degree” n and m×m index M, provided 1?j?n−m. We find they are restrictions of Hecke operators on Siegel modular forms, and we compute their action on Fourier coefficients. Then we restrict the Hecke-Siegel operators T(p), Tj(p²) (n−m<j?n) to Jacobi forms of Siegel degree n, compute their action on Fourier coefficients and on indices, and produce lifts from Jacobi forms of index M to Jacobi forms of index M^′ where detM|detM^′. Finally, we present an explicit choice of matrices for the action of the Hecke operators on Siegel modular forms, and for their restrictions to Jacobi modular forms.     

On a new class of elementary matrices

Summary A new class of elementary matrices, a block-generalisation of plane rotations, is presented and the application in constructing quadratically convergent block diagonalisation algorithms of Jacobi type is discussed.     

An experimental study of approximation algorithms for the joint spectral radius

We describe several approximation algorithms for the joint spectral radius and compare their performance on a large number of test cases. The joint spectral radius of a set Σ of $n \times n$ matrices is the maximal asymptotic growth rate that can be obtained by forming products of matrices from Σ. This quantity is NP-hard to compute and appears in many areas, including in system theory, combinatorics and information theory. A dozen algorithms have been proposed this last decade for approximating the joint spectral radius but little is known about their practical efficiency. We overview these approximation algorithms and classify them in three categories: approximation obtained by examining long products, by building a specific matrix norm, and by using optimization-based techniques. All these algorithms are now implemented in a (freely available) MATLAB toolbox that was released in 2011. This toolbox allows us to present a comparison of the approximations obtained on a large number of test cases as well as on sets of matrices taken from the literature. Finally, in our comparison we include a method, available in the toolbox, that combines different existing algorithms and that is the toolbox’s default method. This default method was able to find optimal products for all test cases of dimension less than four.     

A new numerical method for delay and advanced integro-differential equations

A general formulation is constructed for Jacobi operational matrices of integration, product, and delay on an arbitrary interval. The main purpose of this study is to improve Jacobi operational matrices for solving delay or advanced integro–differential equations. Some theorems are established and utilized to reduce the computational costs. All algorithms can be used for both linear and nonlinear Fredholm and Volterra integro-differential equations with delay. An error estimator is introduced to approximate the absolute error when the exact solution of a given problem is not available. The error of the proposed method is less compared to other common methods such as the Taylor collocation, Chebyshev collocation, hybrid Euler–Taylor matrix, and Boubaker collocation methods. The reliability and efficiency of the proposed scheme are demonstrated by some numerical experiments.     

Hankel Determinants of a Linear Combination of Three Successive Catalan Numbers

We evaluate the determinants of Hankel matrices, whose elements are a linear combination of three successive shifted Catalan numbers. This is done by finding a Jacobi linear functional, such that their moments are, up to a multiplicative constant, the Catalan numbers. The values of such determinants are then expressed in terms of Jacobi polynomials.     

Spectral Density of Jacobi Matrices with Small Deviations

We present several new asymptotic trace formulas for Jacobi matrices whose coefficients satisfy a small deviation condition. Our results extend most of the existing trace formulas for Jacobi matrices.     

Unbounded Jacobi Matrices with a Few Gaps in the Essential Spectrum: Constructive Examples

We give explicit examples of unbounded Jacobi operators with a few gaps in their essential spectrum. More precisely a class of Jacobi matrices whose absolutely continuous spectrum fills any finite number of bounded intervals is considered. Their point spectrum accumulates to +?? and ???. The asymptotics of large eigenvalues is also found.