Solving structured linear systems with large displacement rank (Q954988)

The following problems is studied: For the linear system \((P,Q,\alpha)\), given a \(P\), \(Q\)-generator of length \(\alpha\) for the matrix \(A \in K^{n\times n}\), with \(\alpha \leq n\), and given \(v \in K^n\), find a solution to the equation \(Au=v\), or determine that none exists. This contribution bridges a gap between the approaches of structured and dense linear algebra by providing algorithms of cost \(O^{\sim}(\alpha^{\omega -1}n)\) in the case of Toeplitz-like, Vandermonde-like and Cauchy-like matrices. Integer arithmetic is used for handling indices in arrays. All operations are seen to need unit cost. The proposed algorithms rely on polynomial multiplication and are probabilistic in nature. In the appendix an algorithm, that does not rely on sorting algorithm, is presented for transforming an arbitrary vector in a suitable form for handling.