Name
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 Tu=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 Ø(nlog2n) for a Toeplitz matrix of size n×n. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.laa.2013.01.015 | Linear Algebra and its Applications |
Keywords | Field | DocType |
65F05,13P05,13P10,14Q99 | Discrete mathematics,Combinatorics,Algebra,Polynomial,Remainder,Toeplitz matrix,Syzygy (astronomy),Mathematics,Computational complexity theory,Levinson recursion | Journal |
Volume | Issue | ISSN |
438 | 9 | 0024-3795 |
Citations | PageRank | References |
2 | 0.38 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Houssam Khalil | 1 | 23 | 1.35 |
| Bernard Mourrain | 2 | 1074 | 113.70 |
| Michelle Schatzman | 3 | 29 | 9.21 |