The Stabilization of Weights in the Lanczos and Conjugate Gradient Method

The Lanczos and the Conjugate Gradient method both compute implicitly a sequence of Gauss quadrature approximations to a certain Riemann-Stieltjes integral. In finite precision computations the corresponding weight function will be slightly perturbed. The purpose of this paper is to solve a conjecture posed by Anne Greenbaum and Zdeněk Strakoš on the stabilization of weights for the Gauss quadrature approximations, i.e. in particular we prove that for a tight well separated cluster of Ritz values (nodes) an upper bound for the change in the sum of the corresponding weights can be developed that depends mainly on the ratio of the cluster diameter and the gap in the spectrum. AMS subject classification (2000) 65F10, 65F15, 65F50     

UTV Expansion Pack: Special-purpose rank-revealing algorithms

This collection of Matlab 7.0 software supplements and complements the package UTV Tools from 1999, and includes implementations of special-purpose rank-revealing algorithms developed since the publication of the original package. We provide algorithms for computing and modifying symmetric rank-revealing VSV decompositions, we expand the algorithms for the ULLV decomposition of a matrix pair to handle interference-type problems with a rank-deficient covariance matrix, and we provide a robust and reliable Lanczos algorithm which – despite its simplicity – is able to capture all the dominant singular values of a sparse or structured matrix. These new algorithms have applications in signal processing, optimization and LSI information retrieval. AMS subject classification 65F25     

Solution of sparse rectangular systems using LSQR and CRAIG

We examine two iterative methods for solving rectangular systems of linear equations: LSQR for over-determined systemsAx b, and Craig's method for under-determined systemsAx = b. By including regularization, we extend Craig's method to incompatible systems, and observe that it solves the same damped least-squares problems as LSQR. The methods may therefore be compared on rectangular systems of arbitrary shape.Various methods for symmetric and unsymmetric systems are reviewed to illustrate the parallels. We see that the extension of Craig's method closes a gap in existing theory. However, LSQR is more economical on regularized problems and appears to be more reliable if the residual is not small.In passing, we analyze a scaled augmented system associated with regularized problems. A bound on the condition number suggests a promising direct method for sparse equations and least-squares problems, based on indefiniteLDL ^T factors of the augmented matrix.Dedicated to Professor Åke Björck in honor of his 60th birthdayPresented at the 12th Householder Symposium on Numerical Algebra, Lake Arrowhead, California, June 1993.Partially supported by Department of Energy grant DE-FG03-92ER25117, National Science Foundation grant DMI-9204208, and Office of Naval Research grant N00014-90-J-1242.     

The tensor Golub–Kahan–Tikhonov method applied to the solution of ill-posed problems with a t-product structure

This paper discusses an application of partial tensor Golub–Kahan bidiagonalization to the solution of large-scale linear discrete ill-posed problems based on the t-product formalism for third-order tensors proposed by Kilmer and Martin (M. E. Kilmer and C. D. Martin, Factorization strategies for third order tensors, Linear Algebra Appl., 435 (2011), pp. 641-658). The solution methods presented first reduce a given (large-scale) problem to a problem of small size by application of a few steps of tensor Golub–Kahan bidiagonalization and then regularize the reduced problem by Tikhonov's method. The regularization operator is a third-order tensor, and the data may be represented by a matrix, that is, a tensor slice, or by a general third-order tensor. A regularization parameter is determined by the discrepancy principle. This results in fully automatic solution methods that neither require a user to choose the number of bidiagonalization steps nor the regularization parameter. The methods presented extend available methods for the solution for linear discrete ill-posed problems defined by a matrix operator to linear discrete ill-posed problems defined by a third-order tensor operator. An interlacing property of singular tubes for third-order tensors is shown and applied. Several algorithms are presented. Computed examples illustrate the advantage of the tensor t-product approach, in comparison with solution methods that are based on matricization of the tensor equation.     

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.     

Numerical solution of eigenvalue problems by means of a wavelet‐based Lanczos decomposition

The simple Lanczos process is very efficient for finding a few extreme eigenvalues of a large symmetric matrix. The main task in each iteration step consists in evaluating a matrix‐vector product. It is shown how to apply a fast wavelet‐based product in order to speed up computations. Some numerical results are given for three different monodimensional cases: the harmonic oscillator case, the hydrogenlike atoms, and a problem with a pseudo‐double‐well potential. © 2000 John Wiley & Sons, Inc. Int J Quant Chem 77: 552–562, 2000     

On Lanczos Based Methods for the Regularization of Discrete Ill-Posed Problems

We study hybrid methods for the solution of linear ill-posed problems. Hybrid methods are based on he Lanczos process, which yields a sequence of small bidiagonal systems approximating the original ill-posed problem. In a second step, some additional regularization, typically the truncated SVD, is used to stabilize the iteration. We investigate two different hybrid methods and interpret these schemes as well-known projection methods, namely least-squares projection and the dual least-squares method. Numerical results are provided to illustrate the potential of these methods. This gives interesting insight in to the behavior of hybrid methods in practice.This revised version was published online in October 2005 with corrections to the Cover Date.     

Lanczos向量叠加法的改进及其在高层结构动力分析中的应用

本文柔度法形成高层建筑结构的动力方程,在对现有Ｌａｎｃｏｚ向量叠加法改进后,建立了用改进的Ｌａｎｃｚｏｓ向量叠加法进行高层建筑结构的动力计算的具体步骤与原则。     

A New Critical Region of Quantum Ashkin-Teller Chain

The critical phenomena of the one-dimensional quantum Ashkin-Teller chain are discussed by using the numerical calculation in the quantum conformal field theory. The result shows that there exists a new critical region of the model.     

Direct calculation of long time correlation functions using an optical potential

We present an ℒ︁² method aimed at directly computing autocorrelation functions 〈Φ₀|Φ_t〉 for systems displaying long time recurrences. By making use of a Lanczos scheme, as previously proposed by Wyatt [Chem. Phys. Lett. 121, 301 (1985)], the method avoids explicit time propagation of the wavefunction. The problem associated with spurious recurrences, due to the finite size of the ℒ︁²-box, is solved in terms of an optical potential located in the asymptotic region. The resulting complex representation of the Hamiltonian operator is handled by a complex symmetric Lanczos scheme, which retains the same basic advantages as its real version. The method is illustrated on the ozone photodissociation process which displays a very detailed recurrence structure over a long time period. It is shown that such a direct calculation of the correlation function is about one order of magnitude faster than an actual wavepacket propagation. The accuracy of the method is assessed by comparison to calculations performed without any optical potential but using a very large box size along the dissociation coordinate. © 1998 John Wiley & Sons, Inc. Int J Quant Chem 68: 317–328, 1998