๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A symmetric algorithm for Toeplitz systems

โœ Scribed by A. Melman

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
65 KB
Volume
301
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

โœฆ Synopsis

We derive an algorithm for real symmetric Toeplitz systems with an arbitrary right-hand side. It differs from the Levinson algorithm in that the solution is built up from its middle component(s) outwards, rather than from top to bottom. We then exploit the symmetry of this method by solving separately for the even and odd parts of the right-hand side of the system. On a sequential machine, the complexity of our algorithm for a system of order n is 7/2n 2 + O(n) flops, compared to 4n 2 + O(n) flops for Levinson's algorithm. The algorithm can be extended to nonsymmetric systems, just like Levinson's algorithm.

๐Ÿ“œ SIMILAR VOLUMES

A fast algorithm for solving diagonally
A fast algorithm for solving diagonally dominant symmetric pentadiagonal Toeplitz systems
โœ Jeffrey Mark McNally ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 298 KB

Banded Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Recently, significant advancement has been made in algorithm development of fast parallel scalable methods to solve tridiagonal Toeplitz problems. In this paper we will derive a new al