Structured Linear Algebra

Matrices with a special structure are omnipresent in computer algebra. These are matrices whose elements enjoy a certain repetition, or satisfy certain relationships. More formally, a structured n×n matrix is typically defined by elements O (n), instead of n² for a dense mat arithmetic operations, instead of operations O (n²) for a dense matrix. This article presents a unified algorithm for handling dense structured matrices, such as Toeplitz, Hankel, Vandermonde and Sylvester m with matrices of these classes are linked to calculations with polynomials, which allows the use of fast polynomial multiplication techniques to speed up their manipulation. For example, we can solve a linear system defined by an invertible structured matrix in O (n) operations.