The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

One-sided tangential interpolation for operator-valued Hardy functions on polydisks

All solutions of one-sided tangential interpolation problems with Hilbert norm constraints for operator-valued Hardy functions on the polydisk are described. The minimal norm solution is explicitly expressed in terms of the interpolation data.The research of this author is partially supported by NSF grant DMS 9800704, and by the Faculty Research Assignment grant from the College of William and Mary.     

On the tangential interpolation problem for matrix-valued -functions of two variables

All solutions of a general tangential interpolation problem for matrix-valued Hardy functions of two variables are described. The minimal norm solution is explicitly expressed in terms of the interpolation data.

     

New perturbation bounds for denumerable Markov chains

This paper is devoted to perturbation analysis of denumerable Markov chains. Bounds are provided for the deviation between the stationary distribution of the perturbed and nominal chain, where the bounds are given by the weighted supremum norm. In addition, bounds for the perturbed stationary probabilities are established. Furthermore, bounds on the norm of the asymptotic decomposition of the perturbed stationary distribution are provided, where the bounds are expressed in terms of the norm of the ergodicity coefficient, or the norm of a special residual matrix. Refinements of our bounds for Doeblin Markov chains are considered as well. Our results are illustrated with a number of examples.     

On block minimal residual methods

In the present work, we give some new results for block minimal residual methods when applied to multiple linear systems. Using the Schur complement, we develop new expressions for the approximation obtained, for the corresponding residual and for the Frobenius residual norm. These results could be used to derive new convergence properties for the block minimal residual methods.     

Multilevel Minimal Residual Methods for Nonsymmetric Elliptic Problems

The subject of this paper is to study the performance of multilevel preconditioning for nonsymmetric elliptic boundary value problems. In particular, a minimal residual method with respect to an appropriately scaled norm, measuring the size of the residual projections on all levels, is studied. This norm, induced by the multilevel splitting, is also the basis for a proper stopping criterion. Our analysis shows that the convergence rate of this minimal residual method using the multilevel preconditioner by Bramble, pasciak and Xu is bounded independently of the mesh-size. However, the convergence rate deteriorates with increasing size of the skew-symmetric part. Our numerical results show that by incorporating this into a multilevel cycle starting on the coarsest level, one can save fine-level-iterations and, therefore, computational work.     

AN EXTENDED BLOCK RESTRICTED ISOMETRY PROPERTY FOR SPARSE RECOVERY WITH NON-GAUSSIAN NOISE

We study the recovery conditions of weighted mixed $\ell_2/\ell_p$ minimization for block sparse signal reconstruction from compressed measurements when partial block support information is available. We show theoretically that the extended block restricted isometry property can ensure robust recovery when the data fidelity constraint is expressed in terms of an $\ell_q$ norm of the residual error, thus establishing a setting wherein we are not restricted to Gaussian measurement noise. We illustrate the results with a series of numerical experiments.     

A robust a posteriori estimator for the Residual-free Bubbles method applied to advection-diffusion problems

Summary. We develop the a posteriori error analysis for the RFB method, applied to the linear advection-diffusion problem: the numerical error, measured in suitable norms, is estimated in terms of the numerical residual. The robustness is investiged, in the sense that we prove uniform equivalence between a norm of the numerical residual and a particular norm of the error. Received January 21, 2000 / Published online March 20, 2001     

A posteriori error analysis for numerical approximations of Friedrichs systems

The global error of numerical approximations for symmetric positive systems in the sense of Friedrichs is decomposed into a locally created part and a propagating component. Residual-based two-sided local a posteriori error bounds are derived for the locally created part of the global error. These suggest taking the -norm as well as weaker, dual norms of the computable residual as local error indicators. The dual graph norm of the residual is further bounded from above and below in terms of the norm of where h is the local mesh size. The theoretical results are illustrated by a series of numerical experiments. Received January 10, 1997 / Revised version received March 5, 1998     

A-Posteriori Local Error Estimates of Boundary Element Methods with Some Pseudo-Differential Equations on Closed Curves

In this paper we show local error estimates for the Galerkin finite element method applied to strongly elliptic pseudo-differential equations on closed curves. In these local estimates the right hand sides are obtained as the sum of a local norm of the residual, which is computable, and additional terms of higher order with respect to the computable, and additional terms of higher order with respect to the meshwidth. Hence, asymptotically, here the residual is an error indicator which provides a corresponding self-adaptive boundary element method.     

Convergence properties of some block Krylov subspace methods for multiple linear systems

In the present paper, we give some convergence results of the global minimal residual methods and the global orthogonal residual methods for multiple linear systems. Using the Schur complement formulae and a new matrix product, we give expressions of the approximate solutions and the corresponding residuals. We also derive some useful relations between the norm of the residuals.     

一种新型压缩预处理CGS算法

CGS算法是求解大型非对称线性方程组的常用算法，然而该算法无极小残差性质，因此它常因出现较大的中间剩余向量而出现典型的不规则收敛行为．本根据IRA方法提出了一种压缩预处理CGS方法，数值实验表明这种算法在一定程度上减小了迭代算法在收敛过程中的剩余问题，从而使得算法具有更好的稳定性，该法构造简单，减少了收敛次数，加快了收敛速度．     

A-posteriori residual bounds for Arnoldi’s methods for nonsymmetric eigenvalue problems

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods.     

Necessary conditions for nonconvex distributed control problems governed by elliptic variational inequalities

In 1956, R. Penrose studied best-approximate solutions of the matrix equation AX = B. He proved that A⁺B (where A⁺ is the Moore-Penrose inverse) is the unique matrix of minimal Frobenius norm among all matrices which minimize the Frobenius norm of AX ? B. In particular, A⁺ is the unique best-approximate solution of AX = I. The vector version of Penrose's result (that is, the fact that the vector A⁺b is the best-approximate solution in the Euclidean norm of the vector equation Ax = b) has long been generalized to infinite dimensional Hilbert spaces.In this paper, an infinite dimensional version of Penrose's full result is given. We show that a straightforward generalization is not possible and provide new extremal characterizations (in terms of the Hermitian order) of A⁺ and of the classes of generalized inverses associated with minimal norm solutions of consistent operator equations or with least-squares solutions. For a certain class of operators, we can phrase our characterizations in terms of a whole class of norms (including the Hilbert-Schmidt and the trace norms), thus providing new extremal characterizations even in the matrix case. We treat both operators with closed range and with not necessarily closed range. Finally, we characterize A⁺ as the unique inner inverse of minimal Hilbert-Schmidt norm if ∥A⁺∥₂ < ∞. We give an application of the new extremal characterization to the compensation problem in systems analysis in infinite-dimensional Hilbert spaces.     

Invariants of contact structures from open books

In this note we define three invariants of contact structures in terms of open books supporting the contact structures. These invariants are the support genus (which is the minimal genus of a page of a supporting open book for the contact structure), the binding number (which is the minimal number of binding components of a supporting open book for the contact structure with minimal genus pages) and the norm (which is minus the maximal Euler characteristic of a page of a supporting open book).

     

Minimal Zero Norm Solutions of Linear Complementarity Problems

In this paper, we study minimal zero norm solutions of the linear complementarity problems, defined as the solutions with smallest cardinality. Minimal zero norm solutions are often desired in some real applications such as bimatrix game and portfolio selection. We first show the uniqueness of the minimal zero norm solution for Z-matrix linear complementarity problems. To find minimal zero norm solutions is equivalent to solve a difficult zero norm minimization problem with linear complementarity constraints. We then propose a p norm regularized minimization model with p in the open interval from zero to one, and show that it can approximate minimal zero norm solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, that can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to get desired sparsity. Based on the theoretical results, we design a sequential smoothing gradient method to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and get minimal zero norm solutions of linear complementarity problems.     

Bounds for the least squares distance using scaled total least squares

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the data to make the corrected system compatible. In ordinary least squares (LS) the correction is restricted to the right hand side c, while in scaled total least squares (STLS) [14,12] corrections to both c and B are allowed, and their relative sizes are determined by a real positive parameter . As , the STLS solution approaches the LS solution. Our paper [12] analyzed fundamentals of the STLS problem. This paper presents a theoretical analysis of the relationship between the sizes of the LS and STLS corrections (called the LS and STLS distances) in terms of . We give new upper and lower bounds on the LS distance in terms of the STLS distance, compare these to existing bounds, and examine the tightness of the new bounds. This work can be applied to the analysis of iterative methods which minimize the residual norm, and the generalized minimum residual method (GMRES) [15] is used here to illustrate our theory. Received July 20, 2000 / Revised version received February 28, 2001 / Published online July 25, 2001     

The Local Steiner Problem in Finite-Dimensional Normed Spaces

We develop a general method for proving that certain star configurations in finite-dimensional normed spaces are Steiner minimal trees. This method generalizes the results of Lawlor and Morgan (1994) that could only be applied to differentiable norms. The generalization uses the subdifferential calculus from convex analysis. We apply this method to two special norms. The first norm, occurring in the work of Cieslik, has unit ball the polar of the difference body of the n-simplex (in dimension 3 this is the rhombic dodecahedron). We determine the maximum degree of a given point in a Steiner minimal tree in this norm. The proof makes essential use of extremal finite set theory. The second norm, occurring in the work of Conger (1989), is the sum of the ℓ₁-norm and a small multiple of the ℓ₂ norm. For the second norm we determine the maximum degree of a Steiner point.     

On Domination Conditions for Systems of Minimal Differential Operators Acting in the Space L ∞ $$\mathbb{R}^n $$

In this paper, we consider the linear space of minimal differential operators with constant coefficients which are dominated by systems of minimal operators acting in spaces with uniform norm. In terms of domination conditions, we prove the quasiellipticity test for a given operator; this criterion generalizes a similar result of De Leeuw and Mirkil to elliptic operators.     

Gaussian Curvature Estimates for the Convex Level Sets of Solutions for Some Nonlinear Elliptic Partial Differential Equations

We give lower bound estimates for the Gaussian curvature of convex level sets of minimal surfaces and the solutions to semilinear elliptic equations in terms of the norm of boundary gradient and the Gaussian curvature of the boundary.