Fast algorithms for solving Toeplitz systems of equations using number-theoretic transforms

• Published in: Signal processing 1995-06, Vol.44 (1), p.89-101
• Main Authors: Hsue, Jin-Jen, Yagle, Andrew E.
• Format: Article
• Language: English
• Subjects: Applied sciences; Exact sciences and technology; Fast algorithms; Information, signal and communications theory; Mathematical methods; Number-theoretic transforms; Telecommunications and information theory; Toeplitz matrices
• ISSN: 0165-1684; 1872-7557
• DOI: 10.1016/0165-1684(95)00017-8

Three fast algorithms for solving Toeplitz systems of equations are presented. The algorithms all embed the Toeplitz system in a circulant system, solve the latter using number-theoretic transforms, and then implement the Trench algorithm in reverse, also using number-theoretic transforms. Assuming all system matrix entries are rational numbers, the algorithms avoid roundoff error and any attendant conditioning problems. The first algorithm represents rational numbers with integers in a Galois field. The second algorithm computes the determinant of the system matrix and multiplies the system equation by it, producing an integer solution from which the actual rational solution may be determined. The third algorithm extends the second algorithm by using residue number systems. Numerical examples illustrate the new algorithms, and demonstrate the improvement over FFT-based algorithms in avoiding roundoff error in an ill-conditioned problem. Es werden drei schnelle Algorithmen zur Lösung von Toeplitz-Gleichungssystemen vorgestellt. Alle Algorithmen überführen das Toeplitz System in ein zirkulantes System, lösen dieses unter Anwendung zahlentheoretischer Transformationen und benutzen dann den reversem Trench-Algorithmus, wobei wieder zahlentheoretische Transformationen angewendet werden. Nimmt man für alle Systemmatrizen-Elemente rationale Zahlen an, so vermeiden die Algorithmen Rundungsfehler und die zugehörigen Konditionierungsprobleme. Der erste Algorithmus enthält rationale Zahlen mit Integer-Groβen in einem Galois-Feld. Der zweite Algorithmus berechnet die Determinante der Systemmatrix und multipliziert die Systemgleichung hiermit, wobei eine Integer-Lösung erzeugt wird, von der die eigentliche Lösung abgeleitet werden kann. Der dritte Algorithmus erweitert den zweiten Algorithmus durch Anwendung von Restklassen-Zahlensystemen. Numerische Beispiele veranschaulichen die neuen Algorithmen und zeigen die Verbesserung gegenüber FFT-basierten Algorithmen in Bezug auf die Vermeidung von Rundungsfehlern bei schlecht konditionierten Problemen. Trois algorithmes rapides pour la résolution de systèmes d'équations de type Toeplitz sont présentés. Les algorithmes incorporent tous le systéme Toeplitz dans un système circulant, résolvent le second à l'aide de transformations algébriques, et implantent ensuite l'algorithme de Trench à rebours, également à l'aide de transformations. Sous I'hypothèse que toutes les entrées de la matrice du système sont des nombres rationne