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^2 for a dense mat arithmetic operations, instead of operations O(n^2) 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.