Search

Zeros of rational transfer function matrices R(λ) are the eigenvalues of associated polynomial system matrices P(λ) under minimality conditions. In this paper, we define a structured condition number for a simple eigenvalue λ0 of a (locally) minimal polynomial system matrix P(λ), which in turn is a simple zero λ0 of its transfer function matrix R(λ). Since any rational matrix can be written as the transfer function of a polynomial system matrix, our analysis yields a structured perturbation theory for simple zeros of rational matrices R(λ). To capture all the zeros of R(λ), regardless of whether they are poles, we consider the notion of root vectors. As corollaries of the main results, we pay particular attention to the special case of λ 0 being not a pole of R(λ) since in this case the results get simpler and can be useful in practice. We also compare our structured condition number with Tisseur's unstructured condition number for eigenvalues of matrix polynomials and show that the latter can be unboundedly larger. Finally, we corroborate our analysis by numerical experiments. [ABSTRACT FROM AUTHOR]

Many recent data analysis models are mathematically characterized by a multidimensional total least squares problem with linear equality constraints (TLSE). In this paper, an explicit solution is firstly derived for the multidimensional TLSE problem, as well as the solvability conditions. With applying the perturbation theory of invariant subspace, the multidimensional TLSE problem is proved equivalent to a multidimensional unconstrained weighed total least squares problem in the limit sense. The Kronecker product-based formulae are also given for the normwise, mixed, and componentwise condition numbers of the multidimensional TLSE solution of minimum Frobenius norm, and their computable upper bounds are also provided to reduce the storage and computational cost. All these results are appropriate for the single right-hand-side case and the multidimensional total least squares problem, which are two especial cases of the multidimensional TLSE problem. In numerical experiments, the multidimensional TLSE model is successfully applied to color image deblurring and denoising for the first time, and the numerical results also indicate the effectiveness of the condition numbers. [ABSTRACT FROM AUTHOR]

Kemeny's constant is an interesting and useful quantifier describing the global average behavior of a Markov chain. In this article, we examine the sensitivity of Kemeny's constant to perturbations in the transition probabilities. That is, we consider the problem of generating a condition number for Kemeny's constant to give an indication of the size of the change in its value relative to the size of the perturbation. We provide a structured condition number and determine some illuminating upper and lower bounds which connect the conditioning of Kemeny's constant to well-studied condition numbers for the stationary vector of the Markov chain. We also investigate the behavior of this structured condition number for several infinite families of Markov chains. [ABSTRACT FROM AUTHOR]

Solving a singular linear system for an individual vector solution is an ill-posed problem with a condition number infinity. From an alternative perspective, however, the general solution of a singular system is of a bounded sensitivity as a unique element in an affine Grassmannian. If a singular linear system is given through empirical data that are sufficiently accurate with a tight error bound, a properly formulated general numerical solution uniquely exists in the same affine Grassmannian, enjoys Lipschitz continuity, and approximates the underlying exact solution with an accuracy in the same order as the data. Furthermore, any backward accurate numerical solution vector is an accurate approximation to one of the solutions of the underlying singular system. [ABSTRACT FROM AUTHOR]

Let P : Ω ⊂ C → Cn×n be given by P(λ) := Σm j=0 Ajφj(λ), where φj : Ω → C for j = 0, 1, ..., m are suitable functions. We present an eigenvector-free framework for the sensitivity analysis of eigenvalues of P. We analyze the Fréchet differentiability of a simple eigenvalue of P as a function of P and derive two equivalent representations of the Fr'echet derivative and the gradient of the eigenvalue. Further, we derive three equivalent representations of the condition number cond(λ, P) of a simple eigenvalue λ of P. Specially, we present an eigenvector-free representation of cond(λ, P) which generalizes a result due to Smith [Numer. Math., 10 (1967), pp. 232-240] for a standard eigenvalue problem to the case of a nonlinear eigenvalue problem and provides an alternative viewpoint of the sensitivity of eigenvalues. In the second part, we consider a homogeneous matrixvalued function H : C2 → Cn×n of the form H(c, s) := Σmj=0 Ajψj(c, s), where ψj : C2 → C for j = 0, 1, ..., m are homogeneous functions of degree ℓ. We present a simple and concise eigenvectorfree framework for the sensitivity analysis of eigenvalues of H that avoids the apparatus of projective spaces. We analyze Fréchet differentiability of a simple eigenvalue of H as a function of H and derive two equivalent representations of the Fréchet derivative and the gradient of the eigenvalue. Furthermore, we derive three equivalent representations of the condition number cond((λ, μ), H) of a simple eigenvalue (λ, μ) of H. Our eigenvector-free representation of cond((λ, μ),H) generalizes Smith's eigenvector-free representation of the condition number of a simple eigenvalue of a matrix to the case of a homogeneous nonlinear eigenproblem. [ABSTRACT FROM AUTHOR]

We study the structured condition number of differentiable maps between smooth matrix manifolds, extending previous results to maps that are only R-differentiable for complex manifolds. We present algorithms to compute the structured condition number. As special cases of smooth manifolds, we analyze automorphism groups, and Lie and Jordan algebras associated with a scalar product. For such manifolds, we derive a lower bound on the structured condition number that is cheaper to compute than the structured condition number. We provide numerical comparisons between the structured and unstructured condition numbers for the principal matrix logarithm and principal matrix square root of matrices in automorphism groups as well as for the map between matrices in automorphism groups and their polar decomposition. We show that our lower bound can be used as a good estimate for the structured condition number when the matrix argument is well conditioned. We show that the structured and unstructured condition numbers can differ by many orders of magnitude, thus motivating the development of algorithms preserving structure. [ABSTRACT FROM AUTHOR]

In this paper we present a class of robust and fully algebraic two-level preconditioners for symmetric positive definite (SPD) matrices. We introduce the notion of algebraic local symmetric positive semidefinite splitting of an SPD matrix and we give a characterization of this splitting. This splitting leads to construct algebraically and locally a class of efficient coarse spaces which bound the spectral condition number of the preconditioned system by a number defined a priori. We also introduce the τ-filtering subspace. This concept helps compare the dimension minimality of coarse spaces. Some PDEs-dependant preconditioners correspond to a special case. The examples of the algebraic coarse spaces in this paper are not practical due to expensive construction. We propose a heuristic approximation that is not costly. Numerical experiments illustrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

We compute the exact expected value of the squared condition number for the polynomial eigenvalue problem, when the input matrices have entries coming from the standard complex Gaussian distribution, showing that in general this problem is quite well conditioned. [ABSTRACT FROM AUTHOR]

We present a general framework for the sensitivity and backward perturbation analysis of linear as well as nonlinear multiparameter eigenvalue problems (MEPs). For a general norm on the space of MEPs, we present a comprehensive analysis of the sensitivity of simple eigenvalues of linear and nonlinear MEPs. We consider the condition number cond(λ,W) of a simple eigenvalue λ ϵℂm of an MEP W and derive three equivalent representations of cond(λ,W) of which two are eigenvector-free. Our eigenvector-free representation of cond(λ,W) provides an alternative viewpoint of the sensitivity of λ. We also analyze holomorphic perturbation of a simple eigenvalue of W when W varies holomorphically on a parameter t ϵℂp. For λ ϵℂm, we consider the backward error η (λ,W) of λ as an approximate eigenvalue of W and determine η (λ,W). We construct an optimal perturbation Δ W such that λ is an eigenvalue of W + Δ W and ∥Δ W∥ = η (λ,W). We also consider the backward error η (λ, x,W) of an approximate eigenpair (λ, x) and determine η (λ, x,W). Further, we construct an optimal perturbation Δ W such that W(λ)x+Δ W(λ)x = 0 and ∥Δ W∥ = η (λ, x,W). [ABSTRACT FROM AUTHOR]

The join set of a finite collection of smooth embedded submanifolds of a mutual vector space is defined as their Minkowski sum. Join decompositions generalize some ubiquitous decompositions in multilinear algebra, namely, tensor rank, Waring, partially symmetric rank, and block term decompositions. This paper examines the numerical sensitivity of join decompositions to perturbations; specifically, we consider the condition number for general join decompositions. It is characterized as a distance to a set of ill-posed points in a supplementary product of Grassmannians. We prove that this condition number can be computed eficiently as the smallest singular value of an auxiliary matrix. For some special join sets, we characterized the behavior of sequences in the join set converging to the latter's boundary points. Finally, we specialize our discussion to the tensor rank and Waring decompositions and provide several numerical experiments confirming the key results. [ABSTRACT FROM AUTHOR]

We present the Kronecker-product-based formulae for the normwise, mixed, and componentwise condition numbers of the multidimensional total least squares (TLS) problem. For easy estimation, we also exhibit Kronecker-product-free upper bounds for these condition numbers. The upper bound for the normwise condition number is proved to be optimal, greatly improving the results by Gratton et al. for the truncated solution of the ill-conditioned basic TLS problem. As a special case, we also provide a lower bound for the normwise condition number of the classic TLS problem when having a unique solution. These bounds are analyzed in detail. Furthermore, we prove that the tight estimates of mixed and componentwise condition numbers recently given by other authors for the basic TLS problem are exact. Some numerical experiments are performed to illustrate our results. [ABSTRACT FROM AUTHOR]

We state and prove an analogue of the Daleckii--Krein theorem, thus obtaining an explicit formula for the Fréchet derivative of generalized matrix functions. Moreover, we prove the differentiability of generalized matrix functions of real matrices under very mild assumptions. For complex matrices, we argue that, under the same assumptions, generalized matrix functions are real-differentiable but generally not complex-differentiable. Finally, we discuss the application of our results to the study of the condition number of generalized matrix functions. Along our way, we also derive generalized matrix functional analogues of a few classical theorems on polynomial interpolation of classical matrix functions and their derivatives. [ABSTRACT FROM AUTHOR]

Theoretical and computational aspects of matrix inverse trigonometric and inverse hyperbolic functions are studied. Conditions for existence are given, all possible values are charac- terized, and the principal values acos, asin, acosh, and asinh are defined and shown to be unique primary matrix functions. Various functional identities are derived, some of which are new even in the scalar case, with care taken to specify precisely the choices of signs and branches. New results include a \round trip" formula that relates acos(cosA) to A and similar formulas for the other inverse functions. Key tools used in the derivations are the matrix unwinding function and the matrix sign function. A new inverse scaling and squaring type algorithm employing a Schur decomposition and variable-degree Pade approximation is derived for computing acos, and it is shown how it can also be used to compute asin, acosh, and asinh. In numerical experiments the algorithm is found to behave in a forward stable fashion and to be superior to computing these functions via logarithmic formulas. [ABSTRACT FROM AUTHOR]

Estimation of the condition numbers of Vandermonde matrices, motivated by applications to interpolation and quadrature, can be traced back to at least the 1970s. Empirical study has consistently shown that Vandermonde matrices tend to be badly ill-conditioned, with a narrow class of exceptions, such as the matrices of the discrete Fourier transform (hereafter we use the acronym DFT). So far, however, formal support for this empirical observation has been limited to the matrices defined by the real set of knots. We prove that, more generally, any Vandermonde matrix of a large size is badly ill-conditioned unless its knots are more or less equally spaced on or about the circle {x : |x| = 1}. The matrices of the DFT are unitary up to scaling and therefore perfectly conditioned. They are defined by a cyclic sequence of knots, equally spaced on that circle, but we prove that even a slight modification of the knots into the so-called quasi-cyclic sequence on this circle defines badly ill-conditioned Vandermonde matrices. Likewise, we prove that the half-size leading (that is, northwestern) block of a large DFT matrix is badly ill-conditioned. (This result was motivated by an application to preconditioning of an input matrix for Gaussian elimination with no pivoting and for block Gaussian elimination.) Our analysis involves the Ekkart{Young theorem, the Vandermonde-to-Cauchy transformation of matrix structure, our new inversion formula for a Cauchy matrix, and low-rank approximation of its large submatrices. [ABSTRACT FROM AUTHOR]

The leverage scores of a full-column rank matrix A are the squared row norms of any orthonormal basis for range (A). We show that corresponding leverage scores of two matrices A and A + ΔA are close in the relative sense if they have large magnitude and if all principal angles between the column spaces of A and A + ΔA are small. We also show three classes of bounds that are based on perturbation results of QR decompositions. They demonstrate that relative differences between individual leverage scores strongly depend on the particular type of perturbation ΔA. The bounds imply that the relative accuracy of an individual leverage score depends on its magnitude and the two-norm condition of A if ΔA is a general perturbation; the two-norm condition number of A if ΔA is a perturbation with the same normwise row-scaling as A; (to first order) neither condition number nor leverage score magnitude if ΔA is a componentwise row-scaled perturbation. Numerical experiments confirm the qualitative and quantitative accuracy of our bounds. [ABSTRACT FROM AUTHOR]

Motivated by the least squares solver Blendenpik, we investigate three strategies for uniform sampling of rows from m×n matrices Q with orthonormal columns. The goal is to determine, with high probability, how many rows are required so that the sampled matrices have full rank and are well-conditioned with respect to inversion. Extensive numerical experiments illustrate that the three sampling strategies (without replacement, with replacement, and Bernoulli sampling) behave almost identically, for small to moderate amounts of sampling. In particular, sampled matrices of full rank tend to have two-norm condition numbers of at most 10. We derive a bound on the condition number of the sampled matrices in terms of the coherence μ of Q. This bound applies to all three different sampling strategies; it implies a, not necessarily tight, lower bound of O(mμln n) for the number of sampled rows; and it is realistic and informative even for matrices of small dimension and the stringent requirement of a 99 percent success probability. For uniform sampling with replacement we derive a potentially tighter condition number bound in terms of the leverage scores of Q. To obtain a more easily computable version of this bound, in terms of just the largest leverage scores, we first derive a general bound on the two-norm of diagonally scaled matrices. To facilitate the numerical experiments and test the tightness of the bounds, we present algorithms to generate matrices with user-specified coherence and leverage scores. These algorithms, the three sampling strategies, and a large variety of condition number bounds are implemented in the MATLAB toolbox kappa SQ. [ABSTRACT FROM AUTHOR]

The main result of this paper is the formulation of an explicit expression for the condition number of the truncated least squares solution of Ax = b. This expression is given in terms of the singular values of A and the Fourier coefficients of b. The result is derived using the notion of the Fréchet derivative together with the product norm on the data [A, b] and the 2-norm on the solution. Numerical experiments are given to confirm our results by comparing them to those obtained by means of a finite difference approach. [ABSTRACT FROM AUTHOR]

The Schur--Padé algorithm [N. J. Higham and L. Lin, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1056--1078] computes arbitrary real powers At of a matrix A C n x n using the building blocks of Schur decomposition, matrix square roots, and Padé approximants. We improve the algorithm by basing the underlying error analysis on the quantities |(I-A)k|1/k, for several small k, instead of |I-A|. We extend the algorithm so that it computes along with At one or more Fréchet derivatives, with reuse of information when more than one Fréchet derivative is required, as is the case in condition number estimation. We also derive a version of the extended algorithm that works entirely in real arithmetic when the data is real. Our numerical experiments show the new algorithms to be superior in accuracy to, and often faster than, the original Schur--Padé algorithm for computing matrix powers and more accurate than several alternative methods for computing the Fréchet derivative. They also show that reliable estimates of the condition number of At are obtained by combining the algorithms with a matrix norm estimator. [ABSTRACT FROM AUTHOR]

In our previous paper [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1491-1506], we studied the condition metric in the space of maximal rank n x m matrices. Here, we show that this condition metric induces a Lipschitz Riemannian structure on that space. After investigating geodesics in such a nonsmooth structure, we show that the inverse of the smallest singular value of a matrix is a log-convex function along geodesics. We also show that a similar result holds for the solution variety of linear systems. Some of our intermediate results such as those on the second covariant derivative or Hessian of a function with symmetries on a manifold, and those on piecewise self-convex functions, are of independent interest. Those results were motivated by our investigations on the complexity of path-following algorithms for solving polynomial systems. [ABSTRACT FROM AUTHOR]

Let Z be an n X n complex matrix. A decomposition Z = U̅MUH is called an antitriangular Schur decomposition of Z if U is an n x n unitary matrix and M is an n x n antitriangular matrix. The antitriangular Schur decomposition is a useful tool for solving palindromic eigenvalue problems. However, there is no perturbation result for an antitriangular Schur decomposition in the literature. The main contribution of this paper is to give a perturbation bound of such decomposition and show that the bound depends inversely on Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed., where XL and XU are the strictly lower triangular and upper triangular parts of X, XN = XL + XU, and Aup(Y) denotes the strictly upper antitriangular part of Y. The quantity √2/f(M) can be used to characterize the condition number of the decomposition, i.e., when √2/f(M) is large (or small), the decomposition problem is ill-conditioned (or well-conditioned). Numerical examples are presented to illustrate the theoretical result. [ABSTRACT FROM AUTHOR]

In many statistical applications one must solve linear systems involving large, dense, and possibly irregularly structured covariance matrices. These matrices are often ill-conditioned; for example, the condition number increases at least linearly with respect to the size of the matrix when observations of a random process are obtained from a fixed domain. This paper discusses a preconditioning technique based on a differencing approach such that the preconditioned covariance matrix has a bounded condition number independent of the size of the matrix for some important process classes. When used in large scale simulations of random processes, significant improvement is observed for solving these linear systems with an iterative method. [ABSTRACT FROM AUTHOR]

In this paper we consider minimizing the spectral condition number of a positive semidefinite matrix over a nonempty closed convex set Ω. We show that it can be solved as a convex programming problem, and moreover, the optimal value of the latter problem is achievable. As a consequence, when Ω is positive semidefinite representable, it can be cast into a semidefinite programming problem. We then propose a first-order method to solve the convex programming problem. The computational results show that our method is usually faster than the standard interior point solver SeDuMi [J. F. Sturm, Optim. Methods Softw., 11/12 (1999), pp. 625-653] while producing a comparable solution. We also study a closely related problem, that is, finding an optimal preconditioner for a positive definite matrix. This problem is not convex in general. We propose a convex relaxation for finding positive definite preconditioners. This relaxation turns out to be exact when finding optimal diagonal preconditioners. [ABSTRACT FROM AUTHOR]

We derive closed formulas for the condition number of a linear function of the total least-squares solution. Given an overdetermined linear system Ax ≈ b, we show that this condition number can be computed using the singular values and the right singular vectors of [A, b] and A. We also provide an upper botlnd that requires the computation of the largest and the smallest singular value of [A, b] and the smallest singular value of A. In numerical examples, we compare these values and the resulting forward error bounds with the error estimates given by Van Huffel and Vandewalle [The Total Least Squares Problem: Computational Aspects and Analysis, Frontiers Appl. Math. 9, SIAM, Philadelphia, 1991], and we show the limitation of the first order approach. [ABSTRACT FROM AUTHOR]

A sufficient condition for the convexity of a finite product of positive definite quadratic forms is given in terms of the condition numbers of the underlying matrices. When only two factors are involved, the condition is also necessary. This complements and improves a result recently obtained by Zhao [Appl. Math. Optim., 62 (2010), pp. 411-434]. As a special case, a necessary and sufficient condition is given for the Kantorovich function (xTAx)(xT A-1x), where A is positive definite, to be convex. [ABSTRACT FROM AUTHOR]

We define in the space of n×m matrices of rank n, n ≤ m, the condition Riemannian structure as follows: For a given matrix A the tangent space at A is equipped with the Hermitian inner product obtained by multiplying the usual Frobenius inner product by the inverse of the square of the smallest singular value of A denoted σn(A). When this smallest singular value has multiplicity 1, the function A → log(σn(A)−2) is a convex function with respect to the condition Riemannian structure that is t → log(σn(A(t))−2) is convex, in the usual sense for any geodesic A(t). In a more abstract setting, a function α defined on a Riemannian manifold (M, ± ) is said to be self-convex when log α(γ(t)) is convex for any geodesic in (M, α ±, ). Necessary and sufficient conditions for self-convexity are given when α is C2. When α(x) = d(x,N)−2, where d(x,N) is the distance from x to a C2 submanifold N ⊂Rj, we prove that α is self-convex when restricted to the largest open set of points x where there is a unique closest point in N to x. We also show, using this more general notion, that the square of the condition number ∙A∙F /σn(A) is self-convex in projective space and the solution variety. [ABSTRACT FROM AUTHOR]

Suppose Gp×n is a real random matrix whose elements are independent and identically distributed standard normal random variables. Let Wp×p = Gp×nGT n×p, which is the usual Wishart matrix. In addition, let λ1 > λ2 > · · · > λp > 0 and σ1 > σ2 > · · · > σp > 0 denote the distinct eigenvalues of the matrix Wp×p and singular values of Gp×n, respectively. The 2-norm condition number of Gp×n is κ2(Gp×n) = σ λ1/λp = σ1/σp, the square root of the ratio of largest to smallest eigenvalues of the Wishart matrix. In this article we derive an exact expression, albeit somewhat complex, for the probability density function of κ2 Gp×n). [ABSTRACT FROM AUTHOR]

Scaling is a commonly used technique for standard eigenvalue problems to improve the sensitivity of the eigenvalues. In this paper we investigate scaling for generalized and polynomial eigenvalue problems (PEPs) of arbitrary degree. It is shown that an optimal diagonal scaling of a PEP with respect to an eigenvalue can be described by the ratio of its normwise and componentwise condition number. Furthermore, the effect of linearization on optimally scaled polynomials is investigated. We introduce a generalization of the diagonal scaling by Lemonnier and Van Dooren to PEPs that is especially effective if some information about the magnitude of the wanted eigenvalues is available and also discuss variable transformations of the type λ = αμ for PEPs of arbitrary degree. [ABSTRACT FROM AUTHOR]

We derive absolute perturbation bounds for the coefficients of the characteristic polynomial of a n x n complex matrix. The bounds consist of elementary symmetric functions of singular values, and suggest that coefficients of normal matrices are better conditioned with regard to absolute perturbations than those of general matrices. When the matrix is Hermitian positivedefinite, the bounds can be expressed in terms of the coefficients themselves. We also improve absolute and relative perturbation bounds for determinants. The basis for all bounds is an expansion of the determinant of a perturbed diagonal matrix. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the condition number of a low rank modification of a matrix. Analytical results show that the minimum, which is not necessarily unique, can be obtained and expressed by a small number of eigenpairs or singular pairs. The symmetric and the nonsymmetric cases are analyzed, and numerical experiments illustrate the analytical observations. [ABSTRACT FROM AUTHOR]

An efficient method is developed for computation of eigenvalues and eigenvectors with high relative precision in the Sturm-Liouville problem with strongly varying coefficients. Accuracy of the method is independent of the traditional condition number. New structured condition numbers for nonmultiple eigenvalues are introduced. [ABSTRACT FROM AUTHOR]

This paper investigates the effect of structure-preserving perturbations on the eigenvalues of linearly and nonlinearly structured eigenvalue problems. Particular attention is paid to structures that form Jordan algebras, Lie algebras, and automorphism groups of a scalar product. Bounds and computable expressions for structured eigenvalue condition numbers are derived for these classes of matrices, which include complex symmetric, pseudo-symmetric, persymmetric, skewsymmetric, Hamiltonian, symplectic, and orthogonal matrices. In particular we show that under reasonable assumptions on the scalar product, the structured and unstructured eigenvalue condition numbers are equal for structures in Jordan algebras. For Lie algebras, the effect on the condition number of incorporating structure varies greatly with the structure. We identify Lie algebras for which structure does not affect the eigenvalue condition number. [ABSTRACT FROM AUTHOR]

The standard way of solving the polynomial eigenvalue problem of degree m in n × n matrices is to ‘linearize’ to a pencil in mn × mn matrices and solve the generalized eigenvalue problem. For a given polynomial, P, infinitely many linearizations exist and they can have widely varying eigenvalue condition numbers. We investigate the conditioning of linearizations from a vector space 픻핃(P) of pencils recently identified and studied by Mackey, Mackey, Mehl, and Mehrmann. We look for the best conditioned linearization and compare the conditioning with that of the original polynomial. Two particular pencils are shown always to be almost optimal over linearizations in 픻핃(P) for eigenvalues of modulus greater than or less than 1, respectively, provided that the problem is not too badly scaled and that the pencils are linearizations. Moreover, under this scaling assumption, these pencils are shown to be about as well conditioned as the original polynomial. For quadratic eigenvalue problems that are not too heavily damped, a simple scaling is shown to convert the problem to one that is well scaled. We also analyze the eigenvalue conditioning of the widely used first and second companion linearizations. The conditioning of the first companion linearization relative to that of P is shown to depend on the coefficient matrix norms, the eigenvalue, and the left eigenvectors of the linearization and of P. The companion form is found to be potentially much more ill conditioned than P, but if the 2-norms of the coefficient matrices are all approximately 1 then the companion form and P are guaranteed to have similar condition numbers. Analogous results hold for the second companion form. Our results are phrased in terms of both the standard relative condition number and the condition number of Dedieu and Tisseur [Linear Algebra Appl., 358 (2003), pp. 71–94] for the problem in homogeneous form, this latter condition number having the advantage of applying to zero and infinite eigenvalues. [ABSTRACT FROM AUTHOR]

Let Ā be an arbitrary matrix and let A be a slight random perturbation of Ā. We prove that it is unlikely that A has a large condition number. Using this result, we prove that it is unlikely that A has large growth factor under Gaussian elimination without pivoting. By combining these results, we show that the smoothed precision necessary to solve Ax = b, for any b, using Gaussian elimination without pivoting is logarithmic. Moreover, when Ā is an all-zero square matrix, our results significantly improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan (SIAM J. Matrix Anal. Appl., 18 (1997), pp. 499-517). [ABSTRACT FROM AUTHOR]

Invariant subspaces of structured matrices are sometimes better conditioned with respect to structured perturbations than with respect to general perturbations. Sometimes they are not. This paper proposes an appropriate condition number c…, for invariant subspaces subject to structured perturbations. Several examples compare c… with the unstructured condition number. The examples include block cyclic, Hamiltonian, and orthogonal matrices. This approach extends naturally to structured generalized eigenvalue problems such as palindromic matrix pencils. [ABSTRACT FROM AUTHOR]

For an n × n tridiagonal matrix we exploit the structure of its QR factorization to devise two new algorithms for computing the 1-norm condition number in O(n) operations. The algorithms avoid underflow and overflow, and are simpler than existing algorithms since tests are not required for degenerate cases. An error analysis of the first algorithm is given, while the second algorithm is shown to be competitive in speed with existing algorithms. We then turn our attention to an n × n diagonal-plus-semiseparable matrix, A, for which several algorithms have recently been developed to solve Ax = b in O(n) operations. We again exploit the QR factorization of the matrix to present an algorithm that computes the 1-norm condition number in O(n) operations. [ABSTRACT FROM AUTHOR]

Let Gm × n be an m × n real random matrix whose elements are independent and identically distributed standard normal random variables, and let ?2(Gm × n) be the 2-norm condition number of Gm × n. We prove that, for any m ≥ 2, n ≥ 2, and x ≥ ∣n - m∣ + 1, ?2(Gm × n) satisfies "Multiple line equation(s) cannot be represented in ASCII text", where 0.245 ≤ c ≤ 2.000 and 5.013 ≤ c ≤ 6.414 are universal positive constants independent of m, n, and x. Moreover, for any m ≥ 2 and n ≥ 2, E(log ?2(Gm × n)) < log n/∣n-m∣+1 +2.258. A similar pair of results for complex Gaussian random matrices is also established. [ABSTRACT FROM AUTHOR]

Let $\kappa$ be the condition number of an $m$-by-$n$ matrix with independent standard Gaussian entries, either real ($\beta = 1$) or complex ($\beta = 2$). The major result is the existence of a constant $C$ (depending on $m$, $n$, and $\beta$) such that $P[\kappa > x] n$. Traditional methods for solving such nonsquare generalized eigenvalue problems $(A - \lambda B)\underline{v} = \underline{0}$ are expected to lead to no solutions in most cases. In this paper we propose a different treatment: We search for the minimal perturbation to the pair $(A,B)$ such that these solutions are indeed possible. Two cases are considered and analyzed: (i) the case when $n=1$ (vector pencils); and (ii) more generally, the $n>1$ case with the existence of one eigenpair. For both, this paper proposes insight into the characteristics of the described problems along with practical numerical algorithms toward their solution. We also present a simplifying factorization for such nonsquare pencils, and some relations to the notion of pseudospectra. [ABSTRACT FROM AUTHOR]

Let $T = L \Omega L^t$ be an invertible, unreduced, indefinite tridiagonal symmetric matrix with $\Omega$ a diagonal signature matrix. We provide error bounds on the (relative) change in an eigenvalue and the angular change in its eigenvector when the entries in $L$ suffer small relative changes. Our results extend those of Demmel and Kahan for $\Omega = I$. The relative condition number for an eigenvalue exceeds by 1 its absolute condition number as an eigenvalue of $\Omega L^t L$. The condition number of an eigenvector is a weighted sum of the relative separations of the eigenvalue from each of the others. A small example shows that very small eigenpairs can be robust even when the large eigenvalues are extremely sensitive. When $L$ is well conditioned for inversion, then all eigenvalues are robust and the eigenvectors depend only on the relative separations. [ABSTRACT FROM AUTHOR]

Let A be an m*m real random matrix with independently and identically distributed standard Gaussian entries. We prove that there exist universal positive constants c and C such that the tail of the probability distribution of the condition number κ(A) satisfies the inequalities c/x < P{κ(A) > mx} < C/x for every x > 1. The proof requires a new estimation of the joint density of the largest and the smallest eigenvalues of AT A which follows from a formula for the expectation of the number of zeros of a certain random field defined on a smooth manifold. [ABSTRACT FROM AUTHOR]

We explore the computation of roots of polynomials via eigenvalue problems. In particular, we look at the case when the leading coefficient is relatively very small. We argue that the companion matrix algorithm (used, for instance, by the Matlab roots function) is inaccurate in this case. The accuracy problem is addressed by using matrix pencils instead. This improvement can be predicted from the backward error bound of Edelman and Murakami (for companion matrices) versus the bound of Van Dooren and Dewilde (for pencils). We then show how to extend the accurate algorithm to Bézier polynomials and present computational experiments. [ABSTRACT FROM AUTHOR]

In earlier papers, the Bauer­Fike technique was applied to the eigenvalue problem Ax = λx General multiple eigenvalues were dealt with and perturbation results were obtained for individual as well as clusters of eigenvalues. In this paper, we shall generalize the technique to the eigenvalue problem for matrix polynomials. Multiple eigenvalues for monic as well as regular matrix polynomials will be considered. [ABSTRACT FROM AUTHOR]

Let A,B be two matrices having the same number of columns, and let (AT,BT)T have full column rank. Certain normwise condition numbers for a finite generalized singular value (GSV) of the matrix pair {A,B} are defined, and explicit expressions of the condition numbers for a simple, nonzero GSV are derived. Moreover, a normwise backward error of {A,B} with respect to an approximate GSV and an associated approximate generalized singular vector group is also defined, and a computable formula of the backward error is obtained. The results are illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

Backward errors and condition numbers are defined and evaluated for eigenvalues and eigenvectors of generalized eigenvalue problems. Both normwise and componentwise measures are used. Unstructured problems are considered first, and then the basic definitions are extended so that linear structure in the coefficient matrices (for example, Hermitian, Toeplitz, Hamiltonian, or band structure) is preserved by the perturbations. [ABSTRACT FROM AUTHOR]

New perturbation results for the two different algebraic Riccati equations (continuous time and discrete time) are derived in a uniform manner. The new results are illustrated by numerical examples. [ABSTRACT FROM AUTHOR]