On adaptive weighted polynomial preconditioning for Hermitian positive definite matrices

by Bernd Fischer

Publisher: Research Institute for Advanced Computer Science, NASA Ames Research Center, Publisher: National Technical Information Service, distributor in [Moffett Field, Calif.], [Springfield, Va

Written in English
Published: Downloads: 446
Share This

Edition Notes

StatementBernd Fischer and Roland W. Freund.
Series[NASA contractor report] -- NASA CR-197946., RIACS technical report -- 92.09., NASA contractor report -- NASA CR-197946., RIACS technical report -- TR 92.09.
ContributionsFreund, Roland W., Research Institute for Advanced Computer Science (U.S.)
The Physical Object
FormatMicroform
Pagination1 v.
ID Numbers
Open LibraryOL17006443M
OCLC/WorldCa33018748

  Existing work on multigrid for Toeplitz systems. Multigrid methods for symmetric positive definite Toeplitz matrices were first proposed by Fiorentino and Serra for the univariate and the block case in [16] and [17], respectively. In [18] they try to extend their work to indefinite symmetric Toeplitz systems via an additive algorithm. The semester project consists of two parts. The first part, which counts for 10 % of the final grade, will be given in September, and the second part, which counts for 20 %, will be given in the end of October/beginning of November. Package mbend for bending non-positive-definite (symmetric) matrices to positive-definiteness, using weighted and unweighted methods. matrixcalc contains a collection of functions for matrix calculations, special matrices, and tests for matrix properties, e.g., (semi-)positive definiteness; mainly used for teaching and research purposes. Find many great new & used options and get the best deals for Numerical Computation 2 Vol. XVI & II: Methods, Software, and Analysis by Christopher W. Ueberhuber (, Trade Paperback) at the best online prices at eBay! Free shipping for many products!

Inverse of complex Hermitian positive-definite matrix, matrix already factorized by F07FRF: Solution of linear system involving preconditioning matrix generated by applying SSOR to complex sparse non-Hermitian matrix Calculates a robust estimation of a correlation matrix, user-supplied weight function G Multivariate Methods. December Why many linear systems in applications have symmetric positive definite system matrices. Examples of families of problems which have symmetric indefinite matrices: finding minima of problems with positive definite energy form subject to linear constraints, e.g., from Stokes' equations for incompressible fluids and problems arising. SLALTEC CMLIB Common Mathematical Library Computational Methods in Environmental Engineering Spring

On adaptive weighted polynomial preconditioning for Hermitian positive definite matrices by Bernd Fischer Download PDF EPUB FB2

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 by:   The conjugate gradient algorithm for solving Hermitian positive definite linear systems is usually combined with preconditioning in order On adaptive weighted polynomial preconditioning for Hermitian positive definite matrices book 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 Cited by:   On Polynomial Preconditioning and Asymptotic Convergence Factors for Indefinite Hermitian Matrices Roland Freund RIACS, Mail Stop NASA Ames Research Center Moffett Field, California and Institut f Angewandte Mathematik and Statistik Universit Wiirzburg D Wiirzburg, Germany Dedicated to Gene Golub, Richard Varga, and David Young Submitted by Cited by:   Ashby, S.

F., Manteuffel, T. A., Otto, J. S.: A comparison of adaptive Chebyshev and least squares polynomial preconditioning for Hermitian positive definite linear systems.

SIAM Journal of Scientific and Statistical Computing 13 () 1–29 CrossRef Google ScholarCited by: 1. In this thesis we examine the use of polynomial preconditioning in CG methods for both hermitian positive definite and indefinite matrices.

Such preconditioners are easy to employ and well-suited. Fischer and R.W. Freund, On adaptive weighted polynomial preconditioning for Hermitian positive definite matrices, ReportRIACS, NASA Ames Research Center, Moffett Field, CA. Google Scholar [4].

Positive definite matrices, Schur complements, and generalized eigenvalue problems 4. On Adaptive Weighted Polynomial Preconditioning for Hermitian Positive Definite Matrices.

Matrix Analysis, Cambridge University Press, New York. Review and Miscellanea. Eigenvalues, Eigenvectors, and Similarity.

Unitary Equivalence and Normal Matrices. Canonical Forms. Hermitian and Symmetric Matrices. Norms for Vectors and Matrices. Location and Perturbation of Eigenvalues. Positive Definite Matrices. Horn and C. Johnson (). When A is hermitian indefinite (hid), the conjugate residual method may be used.

If A is ill-conditioned, these methods may converge slowly, in which case a preconditioner is needed. In this thesis we examine the use of polynomial preconditioning in CG methods for both hermitian positive definite and indefinite matrices. Since this is a multiple of a characteristic polynomial of a Hermitian matrix, it must be real-rooted.

The general positive semidefinite case is handled by taking a limit of positive definite matrices, and recalling that the limit along each univariate restriction must be real-rooted or zero.

Remark (Helton-Vinnikov Theorem). Polynomial preconditioners So far, we have described preconditioners in only one of two classes: those that approximate the coefficient matrix, and where linear systems with the preconditioner as coefficient matrix are easier to solve than the original system.

The Application of Leja Points to Richardson Iteration and Polynomial Preconditioning Lothar Reiche] Department of Mathematics University of Kentucky Lexington, Kentucky Dedicated to Gene Golub, Richard Varga, and David Young Submitted by Wilhelm Niethammer ABSTRACT Let Ax = b be a linear system of algebraic equations with a large nonhermitian matrix A, and let Q(A) denote.

Positive definite banded CPBDI-C Compute the determinant of a complex Hermitian positive SPBDI-S definite band matrix using the factors computed by CPBCO or DPBDI-D CPBFA.

Eigenvalues, eigenvectors EISDOC -A Documentation for EISPACK, a collection of subprograms for solving matrix. Spring Numerical Methods for Partial Differential Equations Prof. Steven G. Johnson, Dept. of Mathematics Overview.

This is the home page for the course at MIT in Springwhere the syllabus, lecture materials, problem sets, and other miscellanea are posted.

Gauss quadrature can be naturally generalized to approximate quasi-definite linear functionals [1], where the interconnections with formal orthogonal polynomials, Padé approximants, complex Jacobi matrices and Lanczos algorithm are analogous to those in the positive definite case.

This method was devised by Hestenes and Stiefel in the early s for the case of a symmetric and positive definite matrix. It has the advantage of being implementable using a three-term recursion. For non-Hermitian matrices, the best-known member may be the GMRES method.

It is shown how the special shift structure of A can be preserved by using polynomial precon-ditioning, and results on the optimal choice of the polynomial preconditioner are given.

Also, we report on some numerical experiments for matrices arising from finite difference approximations to the complex Helmholtz equation.

AbstractIn this paper, we propose a relaxed block splitting preconditioner for a class of complex symmetric indefinite linear systems to accelerate the convergence rate of the Krylov subspace iteration method and the relaxed preconditioner is much closer to the original block two-by-two coefficient matrix.

We study the spectral properties and the eigenvector distributions of the corresponding. Freund, On conjugate gradient type methods and polynomial preconditioners for a class of complex non-hermitian matrices, Numer.

Math. 57 (), no. 1, – Crossref. Approximate Inverse Preconditioning for Shifted Linear Systems, BIT Numerical Mathematics, 43 (), pp. PDF File. Benzi and M. Tuma. A Robust Incomplete Factorization Preconditioner for Positive Definite Matrices, Numerical Linear Algebra with Applications, 10 (), pp.

PDF File. Benzi. Bernd Fischer and Roland W. Freund On adaptive weighted polynomial preconditioning for Hermitian positive definite matrices Element Method Giuseppe Fiorentino and Stefano Serra Multigrid methods for symmetric positive definite block Toeplitz matrices with.

More generally, if the matrix A has a special form, one can sometimes take advantage of this to have a more efficient Ax=b solver, for example: Hermitian positive-definite (Cholesky), tridiagonal or banded (linear-time solvers), lower/upper triangular (forward/backsubstitution), sparse (mostly zero—sparse-direct and iterative solvers, to be.

[13] H. WIMMER, Discrete-time stability of a class of hermitian polynomial matrices with positive semidefinite coefficients, to appear in Matrix Methods: Theory and Algorithms, V. Olshevsky and E. Tyrtyshnikov, Editors, to be published by World Scientific.

c Paper OAM,Zagreb Operators and Matrices [email protected] Tan X () Shifted SSOR-like preconditioner for non-Hermitian positive definite matrices, Numerical Algorithms,(), Online publication date: 1-May Dykes L, Noschese S and Reichel L () Circulant preconditioners for discrete ill-posed Toeplitz systems, Numerical Algorithms,(), Online publication date: 1.

We prove convergence for the class of Stieltjes functions of Hermitian positive definite matrices. We also propose a modification of the Arnoldi method which guarantees convergence for positive real matrices. SIAM J. Matrix Anal.

Appl., 35(4), • Lanczos algorithm — Arnoldi, specialized for positive-definite matrices • QR algorithm • Jacobi eigenvalue algorithm — select a small submatrix which can be diagonalized exactly, and repeat • Jacobi rotation — the building block, almost a Givens rotation • Jacobi method for complex Hermitian matrices.

Computes all eigenvalues and eigenvectors of real symmetric positive definite tridiagonal matrix, reduced from complex Hermitian positive definite matrix: F08JVF: Computes all eigenvalues and, optionally, eigenvectors of a real symmetric tridiagonal matrix or a complex Hermitian matrix reduced to this form (divide-and-conquer) F08JYF.

A comprehensive, must-have handbook of matrix methods with a unique emphasis on statistical applications This timely book, A Matrix Handbook for Statisticians, provides a comprehensive, encyclopedic treatment of matrices as they relate to both statistical concepts and methodologies.

Written by an experienced authority on matrices and statistical theory, this handbook is organized by topic. This work develops a fully robust and efficient preconditioning strategy for solving these systems. Drawing on parabolic inf-sup theory, we first construct a left preconditioner that transforms the linear system to a symmetric positive definite problem to be solved by.

On Adaptive Weighted Polynomial Preconditioning for Hermitian Positive Definite Matrices Bernd Fischer and Roland W. Freund The Research Institute for Advanced P-regular splittings of a hermitian positive definite matrix; for example, see [23], r let A = Aj be a hermitian positive definite matrix, and let Dj, 1.

Solves a real symmetric or complex Hermitian positive definite banded system of linear equations, with coefficient matrix previously factorized by nag_sym_bnd_lin_fac Module nag_sparse_prec - Sparse Matrix Preconditioner Set-up and Solve.Numerical testing results are also reported.

As another application we show a connection between the proposed algorithms and the conjugate gradient (CG) algorithm for positive definite linear systems. Volker Mehrmann, Vanni Noferini, Francoise Tisseur, and Hongguo Xu, On the sign characteristics of Hermitian matrix polynomials.Stieltjes matrix — symmetric positive definite with non-positive off-diagonal entries Hilbert matrix — example of a matrix which is extremely ill-conditioned (and thus difficult to handle) Wilkinson matrix — example of a symmetric tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues.