Stable and Efficient Algorithms for Structured Systems of Linear Equations (Q4389075)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1150977
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Stable and Efficient Algorithms for Structured Systems of Linear Equations |
scientific article; zbMATH DE number 1150977 |
Statements
Stable and Efficient Algorithms for Structured Systems of Linear Equations (English)
0 references
11 May 1998
0 references
structured systems
0 references
displacement equation
0 references
error analysis
0 references
fast algorithm
0 references
Toeplitz matrix
0 references
Hankel matrix
0 references
Cauchy-like matrix
0 references
Gaussian elimination
0 references
pivoting
0 references
numerical experiments
0 references
0.8670584559440613
0 references
0.8644579648971558
0 references
A Cauchy-like matrix has the form \[ C= \Biggl({a^T_i b_j\over \omega_i-\lambda_j}\Biggr)_{1\leq i,j\leq n}\qquad (a_i, b_j\in\mathbb{R}^\alpha), \] where \(\alpha\ll n\). It satisfied a so-called displacement equation, i.e., \[ \Omega C- C\Lambda= A\cdot B\qquad (A\in\mathbb{R}^{n\times\alpha}, B\in\mathbb{R}^{\alpha\times n}). \] The author studies variations of a fast Gaussian elimination algorithm with partial or complete pivoting for Cauchy-like matrices, working systematically with the displacement equation. He describes algorithms that avoid internal element growths and therefore have better backward error properties than the existing methods. The solution of Toeplitz, Hankel and Toeplitz-plus-Hankel matrices can be reduced (in more than one way) to solutions of linear systems with a Cauchy-like matrix. The author discusses implementation techniques that further reduce execution. He presents a careful error analysis, flow counts and extensive numerical experiments that show the superiority of the newly developed methods.
0 references