A note on the normwise perturbation theory for the regular generalized eigenproblem

In this paper, we present a normwise perturbation theory for the regular generalized eigenproblem Ax = λBx, when λ is a semi-simple and finite eigenvalue, which departs from the classical analysis with the chordal norm [9]. A backward error and a condition number are derived for a choice of flexible measure to represent independent perturbations in the matrices A and B. The concept of optimal backward error associated with an eigenvalue only is also discussed. © 1998 John Wiley & Sons, Ltd.     

A posteriori error estimate for computing tr(f(A)) by using the Lanczos method

An outstanding problem when computing a function of a matrix, f(A), by using a Krylov method is to accurately estimate errors when convergence is slow. Apart from the case of the exponential function that has been extensively studied in the past, there are no well‐established solutions to the problem. Often, the quantity of interest in applications is not the matrix f(A) itself but rather the matrix–vector products or bilinear forms. When the computation related to f(A) is a building block of a larger problem (e.g., approximately computing its trace), a consequence of the lack of reliable error estimates is that the accuracy of the computed result is unknown. In this paper, we consider the problem of computing tr(f(A)) for a symmetric positive‐definite matrix A by using the Lanczos method and make two contributions: (a) an error estimate for the bilinear form associated with f(A) and (b) an error estimate for the trace of f(A). We demonstrate the practical usefulness of these estimates for large matrices and, in particular, show that the trace error estimate is indicative of the number of accurate digits. As an application, we compute the log determinant of a covariance matrix in Gaussian process analysis and underline the importance of error tolerance as a stopping criterion as a means of bounding the number of Lanczos steps to achieve a desired accuracy.     

Possible numbers of ones in the squares of 0–1 matrices with a given rank

For a symmetric 0–1 matrix A, we give the number of ones in A ² when rank(A) = 1, 2, and give the maximal number of ones in A ² when rank(A) = k (3 ≤ k ≤ n). The sufficient and necessary condition under which the maximal number is achieved is also obtained. For generic 0–1 matrices, we only study the cases of rank 1 and rank 2.     

The rate of convergence of GMRES on a tridiagonal Toeplitz linear system

The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛ X ⁻¹ and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over A’s spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both A’s spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This paper will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind.     

On the condition numbers associated with the polar factorization of a matrix

We are interested in the calculation of explicit formulae for the condition numbers of the two factors of the polar decomposition of a full rank real or complex m × n matrix A, where m ≥ n. We use a unified presentation that enables us to compute such condition numbers in the Frobenius norm, in cases where A is a square or a rectangular matrix subjected to real or complex perturbations. We denote by σ₁ (respectively σ _n) the largest (respectively smallest) singular value of A, and by K(A) = σ₁/σ _n the generalized condition number of A. Our main results are that the absolute condition number of the Hermitian polar factor is √2(1 + K(A)²)^1/2/(1 + K(A)) and that the absolute condition number of the unitary factor of a rectangular matrix is 1/σ _n. Copyright © 2000 John Wiley & Sons, Ltd.     

Generalized Runge-Kutta methods of order four with stepsize control for stiff ordinary differential equations

Summary GeneralizedA()-stable Runge-Kutta methods of order four with stepsize control are studied. The equations of condition for this class of semiimplicit methods are solved taking the truncation error into consideration. For application anA-stable and anA(89.3°)-stable method with small truncation error are proposed and test results for 25 stiff initial value problems for different tolerances are discussed.     

Componentwise perturbation analyses for the QR factorization

Summary. This paper gives componentwise perturbation analyses for Q and R in the QR factorization A=QR, , R upper triangular, for a given real $m\times n$ matrix A of rank n. Such specific analyses are important for example when the columns of A are badly scaled. First order perturbation bounds are given for both Q and R. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q, so usually the computed Q and R will both have higher accuracy when we use the standard column pivoting strategy. Practical condition estimators are derived. The assumptions on the form of the perturbation are explained and extended. Weaker rigorous bounds are also given. Received April 11, 1999 / Published online October 16, 2000     

Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systemsA _n,mx=b, whereA _n,m is ann×n positive definite block Toeplitz matrix withm×m Toeplitz blocks. In particular we propose a sparse preconditionerP _n,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of bothn andm, even if the condition number ofA _n,m tends to . This leads to iterative methods which require a number of steps independent ofm andn in order to reduce the error by a given factor.     

Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices

We present a structured perturbation theory for the LDU factorization of (row) diagonally dominant matrices and we use this theory to prove that a recent algorithm of Ye (Math Comp 77(264):2195–2230, 2008) computes the L, D and U factors of these matrices with relative errors less than 14n ³ u, where u is the unit roundoff and n × n is the size of the matrix. The relative errors for D are componentwise and for L and U are normwise with respect the “max norm” ||A||_M = max_ij |a_ij|{\|A\|_M = \max_{ij} |a_{ij}|}. These error bounds guarantee that for any diagonally dominant matrix A we can compute accurately its singular value decomposition and the solution of the linear system Ax = b for most vectors b, independently of the magnitude of the traditional condition number of A and in O(n ³) flops.     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001     

Perturbation analysis of the matrix equation

Consider the nonlinear matrix equation X-A^*X^-pA=Q with 0<p1. This paper shows that there exists a unique positive definite solution to the equation. A perturbation bound and the backward error of an approximate solution to this solution is evaluated. We also obtain explicit expressions of the condition number for the unique positive definite solution. The theoretical results are illustrated by numerical examples.     

Spectral condition‐number estimation of large sparse matrices

We describe a randomized Krylov‐subspace method for estimating the spectral condition number of a real matrix A or indicating that it is numerically rank deficient. The main difficulty in estimating the condition number is the estimation of the smallest singular value ${\sigma }_{\min }$ of A. Our method estimates this value by solving a consistent linear least squares problem with a known solution using a specific Krylov‐subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a right singular vector corresponding to ${\sigma }_{\min }$. Extensive experiments show that the method is able to estimate well the condition number of a wide array of matrices. It can sometimes estimate the condition number when running dense singular value decomposition would be impractical due to the computational cost or the memory requirements. The method uses very little memory (it inherits this property from LSQR), and it works equally well on square and rectangular matrices.     

Accurate Solution to Overdetermined Linear Equations with Errors Using L1 Norm Minimization

It has been known for many years that a robust solution to an overdetermined system of linear equations Ax b is obtained by minimizing the L1 norm of the residual error. A correct solution x to the linear system can often be obtained in this way, in spite of large errors (outliers) in some elements of the (m × n) matrix A and the data vector b. This is in contrast to a least squares solution, where even one large error will typically cause a large error in x. In this paper we give necessary and sufficient conditions that the correct solution is obtained when there are some errors in A and b. Based on the sufficient condition, it is shown that if k rows of [A b] contain large errors, the correct solution is guaranteed if (m – n)/n 2k/, where > 0, is a lower bound of singular values related to A. Since m typically represents the number of measurements, this inequality shows how many data points are needed to guarantee a correct solution in the presence of large errors in some of the data. This inequality is, in fact, an upper bound, and computational results are presented, which show that the correct solution will be obtained, with high probability, for much smaller values of m – n.     

Solving linear programs with finite precision: I. Condition numbers and random programs

We define a condition number (A,b,c) for a linear program min x s.t. Ax=b,x0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log (A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution. This work has been substantially funded by a grant from the Research Grants Council of the Hong Kong SAR (project number CityU 1085/02P)     

Free and Non-Free Subgroups of the Group UT(∞, ℤ)

We provide a method to find free groups of rank two in the group of infinite unitriangular matrices. Our groups are generated by two block-diagonal matrices, namely of the form A = diag(C, C, C…), B = diag(I _t , C, C…), where C is a matrix of finite dimension.

We give a necessary and sufficient condition for A and B defined above to generate a free group when C is a transvection. We formulate a sufficient condition to generate a free group, when C is a product of any number of commuting transvections.

We provide a classification of groups defined above, when C is of degree 3 or 4.     

A geometric analysis of Renegar’s condition number,and its interplay with conic curvature

For a conic linear system of the form Ax ∈K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar’s condition number is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, is a representation-dependent measure which is usually difficult to interpret and may lead to overly conservative bounds of computational complexity and/or geometric quantities associated with the set of feasible solutions. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K; furthermore our bounds highlight the role of the singular values of A and their relationship with the condition number. Moreover, by using the notion of conic curvature, we show how Renegar’s condition number can be used to provide both lower and upper bounds on the width of the set of feasible solutions. This complements the literature where only lower bounds have heretofore been developed.     

Generalized Iterated Maximal Essential Extensions of Rings

A necessary and sufficient condition for the existence of GIME(A), the generalized iterated maximal essential extension of an associative ring A, is obtained provided that A is commutative. Some properties of GIME(A) are described, in particular, when A is semiprime or commutative. An example of a prime ring A having no GIME(A) is constructed.2000 Mathematics Subject Classification: 16S70, 13G05, 13E05, 13B02, 13A15     

Sharp Error Terms for Return Time Statistics under Mixing Conditions

We describe the statistics of repetition times of a string of symbols in a stochastic process. Denote by τ _A the time elapsed until the process spells a finite string A and by S _A the number of consecutive repetitions of A. We prove that, if the length of the string grows unboundedly, (1) the distribution of τ _A , when the process starts with A, is well approximated by a certain mixture of the point measure at the origin and an exponential law, and (2) S _A is approximately geometrically distributed. We provide sharp error terms for each of these approximations. The errors we obtain are point-wise and also allow us to get approximations for all the moments of τ _A and S _A . To obtain (1) we assume that the process is φ-mixing, while to obtain (2) we assume the convergence of certain conditional probabilities.      

The complex step approximation to the Fréchet derivative of a matrix function

We show that the Fréchet derivative of a matrix function f at A in the direction E, where A and E are real matrices, can be approximated by Im f(A + ihE)/h for some suitably small h. This approximation, requiring a single function evaluation at a complex argument, generalizes the complex step approximation known in the scalar case. The approximation is proved to be of second order in h for analytic functions f and also for the matrix sign function. It is shown that it does not suffer the inherent cancellation that limits the accuracy of finite difference approximations in floating point arithmetic. However, cancellation does nevertheless vitiate the approximation when the underlying method for evaluating f employs complex arithmetic. The ease of implementation of the approximation, and its superiority over finite differences, make it attractive when specialized methods for evaluating the Fréchet derivative are not available, and in particular for condition number estimation when used in conjunction with a block 1-norm estimation algorithm.     

Probabilistic Analysis of Condition Numbers for Linear Programming

In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C _R(A) introduced by Renegar (Ref. 2).