Abstract

Many structured linear systems arise from problems in polynomial algebra. When this is the case, algorithms from computer algebra, such as the fast Fourier transform, can be used to design faster linear system solvers. In this talk, I will describe some recent work and open problems on the complexity of such structured linear systems.