A classical inequality due to Bernstein which estimates the norm of polynomials on any given ellipse in terms of their norm on any smaller ellipse with the same foci is examined. For the uniform and a certain weighted uniform norm, and for the case that the two ellipses are not too close, sharp estimates of this type were derived and the corresponding extremal polynomials were determined. These Bernstein type inequalities are closely connected with certain constrained Chebyshev approximation...
Topics: NASA Technical Reports Server (NTRS), CHEBYSHEV APPROXIMATION, ELLIPSES, INEQUALITIES, POLYNOMIALS,...
New and sharp estimates are derived for the growth in the complex plane of polynomials known to have a curved majorant on a given ellipse. These so-called Bernstein type inequalities are closely connected with certain constrained Chebyshev approximation problems on ellipses. Also presented are some new results for approximation problems of this type.
Topics: NASA Technical Reports Server (NTRS), CHEBYSHEV APPROXIMATION, ELLIPSES, INEQUALITIES, POLYNOMIALS,...
Explicitly solvable real Chebyshev approximation problems on the unit interval are typically characterized by simple error curves. A similar principle is presented for complex approximation problems with error curves induced by sine polynomials. As an application, some new explicit formulae for complex best approximations are derived.
Topics: NASA Technical Reports Server (NTRS), CHEBYSHEV APPROXIMATION, POLYNOMIALS, SINE SERIES, COMPLEX...
Systems of linear equations with Toeplitz coefficient matrices arise in many important applications. The classical Levinson algorithm computes solutions of Toeplitz systems with only O(n(sub 2)) arithmetic operations, as compared to O(n(sub 3)) operations that are needed for solving general linear systems. However, the Levinson algorithm in its original form requires that all leading principal submatrices are nonsingular. An extension of the Levinson algorithm to general Toeplitz systems is...
Topics: NASA Technical Reports Server (NTRS), LINEAR EQUATIONS, MATRICES (MATHEMATICS), POLYNOMIALS,...
We consider conjugate gradient type methods for the solution of large sparse linear system Ax equals b with complex symmetric coefficient matrices A equals A(T). Such linear systems arise in important applications, such as the numerical solution of the complex Helmholtz equation. Furthermore, most complex non-Hermitian linear systems which occur in practice are actually complex symmetric. We investigate conjugate gradient type iterations which are based on a variant of the nonsymmetric Lanczos...
Topics: NASA Technical Reports Server (NTRS), COEFFICIENTS, COMPLEX SYSTEMS, CONJUGATE GRADIENT METHOD,...
The problem is that of finding among all polynomials of degree at most n and normalized to be 1 at c the one with minimal uniform norm on Epsilon. Here, Epsilon is a given ellipse with both foci on the real axis and c is a given real point not contained in Epsilon. Problems of this type arise in certain iterative matrix computations and, in this context, it is generally believed and widely referenced that suitably normalized Chebyshev polynomials are optimal for such constrained approximation...
Topics: NASA Technical Reports Server (NTRS), CHEBYSHEV APPROXIMATION, ITERATION, MATRICES (MATHEMATICS),...
Constrained Chebyshev approximation problems of the type with minimum (p is an element of Pi(sub n):p(c)=1) and maximum (z is an element of E) with /p(z)/ are considered. Here Pi(sub n) denotes the set of all complex polynomials of degree at most n, E is any ellipse in the complex plane, and c is an element of C/E. Such approximation problems arise in the context of optimizing semi-iterative methods for the solution of large, sparse systems of linear equations Ax=b with complex non-Hermitian...
Topics: NASA Technical Reports Server (NTRS), CHEBYSHEV APPROXIMATION, ITERATIVE SOLUTION, LINEAR...
Recently, Freund and Nachtigal have proposed a novel polynominal-based iteration, the quasi-minimal residual algorithm (QMR), for solving general nonsingular non-Hermitian linear systems. Motivated by the QMR method, we have introduced the general concept of quasi-kernel polynomials, and we have shown that the QMR algorithm is based on a particular instance of quasi-kernel polynomials. In this paper, we continue our study of quasi-kernel polynomials. In particular, we derive bounds for the...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, CONVERGENCE, ITERATION, KERNEL FUNCTIONS, LINEAR...
The minimal residual method is studied combined with polynomial preconditioning for solving large linear systems (Ax = b) with indefinite Hermitian coefficient matrices (A). The standard approach for choosing the polynomial preconditioners leads to preconditioned systems which are positive definite. Here, a different strategy is studied which leaves the preconditioned coefficient matrix indefinite. More precisely, the polynomial preconditioner is designed to cluster the positive, resp. negative...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, CHEBYSHEV APPROXIMATION, HERMITIAN POLYNOMIAL,...
The original quasi-minimal residual method (QMR) relies on the three-term look-ahead Lanczos process, to generate basis vectors for the underlying Krylov subspaces. However, empirical observations indicate that, in finite precision arithmetic, three-term vector recurrences are less robust than mathematically equivalent coupled two-term recurrences. Therefore, we recently proposed a new implementation of the QMR method based on a coupled two-term look-ahead Lanczos procedure. In this paper, we...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, ITERATIVE SOLUTION, LINEAR EQUATIONS, MATRICES...
The biconjugate gradient (BCG) method is the natural generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. A novel BCG like approach is presented called the quasi-minimal residual (QMR) method, which overcomes the problems of BCG. An implementation of QMR based on a look-ahead version of the...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, CONJUGATE GRADIENT METHOD, HERMITIAN POLYNOMIAL,...
In recent years, a number of results on the relationships between the inertias of Hermitian matrices and the inertias of their principal submatrices appeared in the literature. We study restricted congruence transformation of Hermitian matrices M which, at the same time, induce a congruence transformation of a given principal submatrix A of M. Such transformations lead to concept of the restricted signature normal form of M. In particular, by means of this normal form, we obtain short proofs of...
Topics: NASA Technical Reports Server (NTRS), EIGENVALUES, HERMITIAN POLYNOMIAL, MATRICES (MATHEMATICS),...
A family of secant methods based on general rank-1 updates was revisited in view of the construction of iterative solvers for large non-Hermitian linear systems. As it turns out, both Broyden's good and bad update techniques play a special role, but should be associated with two different line search principles. For Broyden's bad update technique, a minimum residual principle is natural, thus making it theoretically comparable with a series of well known algorithms like GMRES. Broyden's good...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, HERMITIAN POLYNOMIAL, ITERATIVE SOLUTION, LINEAR...
The nonsymmetric Lanczos method can be used to compute eigenvalues of large sparse non-Hermitian matrices or to solve large sparse non-Hermitian linear systems. However, the original Lanczos algorithm is susceptible to possible breakdowns and potential instabilities. An implementation is presented of a look-ahead version of the Lanczos algorithm that, except for the very special situation of an incurable breakdown, overcomes these problems by skipping over those steps in which a breakdown or...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, EIGENVALUES, HERMITIAN POLYNOMIAL, ITERATIVE...
The authors have proposed a new Krylov subspace iteration, the quasi-minimal residual algorithm (QMR), for solving non-Hermitian linear systems. In the original implementation of the QMR method, the Lanczos process with look-ahead is used to generate basis vectors for the underlying Krylov subspaces. In the Lanczos algorithm, these basis vectors are computed by means of three-term recurrences. It has been observed that, in finite precision arithmetic, vector iterations based on three-term...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, HERMITIAN POLYNOMIAL, ITERATIVE SOLUTION, LINEAR...
The nonsymmetric Lanczos method can be used to compute eigenvalues of large sparse non-Hermitian matrices or to solve large sparse non-Hermitian linear systems. However, the original Lanczos algorithm is susceptible to possible breakdowns and potential instabilities. We present an implementation of a look-ahead version of the Lanczos algorithm which overcomes these problems by skipping over those steps in which a breakdown or near-breakdown would occur in the standard process. The proposed...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, EIGENVALUES, LINEAR SYSTEMS, MATRICES...
It is shown how the look-ahead Lanczos process (combined with a quasi-minimal residual QMR) approach) can be used to develop a robust black box solver for large sparse non-Hermitian linear systems. Details of an implementation of the resulting QMR algorithm are presented. It is demonstrated that the QMR method is closely related to the biconjugate gradient (BCG) algorithm; however, unlike BCG, the QMR algorithm has smooth convergence curves and good numerical properties. We report numerical...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, EIGENVALUES, LINEAR SYSTEMS, MATRICES...
The conjugate gradient algorithm for solving Hermitian positive definite linear systems is usually combined with preconditioning in order to speed up convergence. In recent years, there has been a revival of polynomial preconditioning, motivated by the attractive features of the method on modern architectures. Standard techniques for choosing the preconditioning polynomial are based only on bounds for the extreme eigenvalues. Here a different approach is proposed, which aims at adapting the...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, CHEBYSHEV APPROXIMATION, CONJUGATE GRADIENT...
In recent years, there has been a true revival of the nonsymmetric Lanczos method. On the one hand, the possible breakdowns in the classical algorithm are now better understood, and so-called look-ahead variants of the Lanczos process have been developed, which remedy this problem. On the other hand, various new Lanczos-based iterative schemes for solving nonsymmetric linear systems have been proposed. This paper gives a survey of some of these recent developments.
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, COMPUTER PROGRAMS, ITERATIVE SOLUTION, LINEAR...
The design of iterative schemes for sparse matrix computations often leads to constrained polynomial approximation problems on sets in the complex plane. For the case of ellipses, we introduce a new class of complex polynomials which are in general very good approximations to the best polynomials and even optimal in most cases.
Topics: NASA Technical Reports Server (NTRS), CHEBYSHEV APPROXIMATION, COMPLEX VARIABLES, ELLIPSES,...
The biconjugate gradient (BCG) method is the natural generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. Recently, Freund and Nachtigal have proposed a novel BCG type approach, the quasi-minimal residual method (QMR), which overcomes the problems of BCG. Here, an implementation is presented of QMR...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, CONJUGATE GRADIENT METHOD, HERMITIAN POLYNOMIAL,...
Conjugate gradient type methods are considered for the solution of large linear systems Ax = b with complex coefficient matrices of the type A = T + i(sigma)I where T is Hermitian and sigma, a real scalar. Three different conjugate gradient type approaches with iterates defined by a minimal residual property, a Galerkin type condition, and an Euclidian error minimization, respectively, are investigated. In particular, numerically stable implementations based on the ideas behind Paige and...
Topics: NASA Technical Reports Server (NTRS), CONJUGATE GRADIENT METHOD, ITERATIVE SOLUTION, LINEAR...
