Superfast solution of Toeplitz systems based on syzygy reduction

DOI10.1016/J.LAA.2013.01.015MaRDI QIDQ1947118zbMATH OpenOpenAlexFDO

Authors Houssam Khalil, Michelle Schatzman, Bernard Mourrain

Publication date 12 April 2013

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5798

zbMATH Keywords

algorithmToeplitz matricespolynomial divisionsyzygies of polynomials

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Syzygies, resolutions, complexes and commutative rings (13D02)

Abstract: We present a new superfast algorithm for solving Toeplitz systems. This algorithm is based on a relation between the solution of such problems and syzygies of polynomials or moving lines. We show an explicit connection between the generators of a Toeplitz matrix and the generators of the corresponding module of syzygies. We show that this module is generated by two elements and the solution of a Toeplitz system T u=g can be reinterpreted as the remainder of a vector depending on g, by these two generators. We obtain these generators and this remainder with computational complexity O(n log^2 n) for a Toeplitz matrix of size nxn.

Recommendations

• Publication:4721516
• Toeplitz and Toeplitz-block-Toeplitz matrices and their correlation with syzygies of polynomials
• scientific article; zbMATH DE number 4098609
• A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations
• A Superfast Algorithm for Toeplitz Systems of Linear Equations

Cites work

• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• scientific article; zbMATH DE number 1206418 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 4120318 (Why is no real title available?)
• scientific article; zbMATH DE number 3451988 (Why is no real title available?)
• scientific article; zbMATH DE number 766201 (Why is no real title available?)
• scientific article; zbMATH DE number 921465 (Why is no real title available?)
• scientific article; zbMATH DE number 1445400 (Why is no real title available?)
• A stabilized superfast solver for nonsymmetric Toeplitz systems
• Algebraic methods for Toeplitz-like matrices and operators
• An Algorithm for the Inversion of Finite Toeplitz Matrices
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• Computations with Gohberg-Semencul-type formulas for Toeplitz matrices
• Displacement Structure: Theory and Applications
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Inversion of Toeplitz matrices with only two standard equations
• Multivariate polynomials, duality, and structured matrices

Cited in

(6)

• Superlinear PCG methods for symmetric Toeplitz systems
• A Divide and Conquer Algorithm for the Superfast Solution of Toeplitz-like Systems
• Transformation of the problem of solution of bilevel Toeplitz systems to a polynomial system
• Every matrix is a product of Toeplitz matrices
• Toeplitz and Toeplitz-block-Toeplitz matrices and their correlation with syzygies of polynomials
• scientific article; zbMATH DE number 3994891 (Why is no real title available?)

This page was built for publication: Superfast solution of Toeplitz systems based on syzygy reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1947118)