A framework for polynomial preconditioners based on fast transforms I: Theory

Optimal and superoptimal approximations of a complex square matrix by polynomials in a normal basis matrix are considered. If the unitary transform associated with the eigenvectors of the basis matrix is computable using a fast algorithm, the approximations may be utilized for constructing preconditioners. Theorems describing how the parameters of the approximations could be efficiently computed are given, and for special cases earlier results by other authors are recovered. Also, optimal and superoptimal approximations for block matrices are determined, and the same type of theorems as for the point case are proved.