On rank and null space computation of the generalized Sylvester matrix (Q5962121)

A Sylvester matrix associated with a polynomial is a particular type of Toeplitz matrix constructed from the coefficients of the polynomial. A generalized Sylvester matrix is obtained by stacking \(m+1\) Sylvester matrices (associated with \(m+1\) different polynomials) on top of each other. The paper under review is concerned with the efficient computation of the rank and null space of such a matrix. For this purpose, the rows of the generalized Sylvester matrix are reordered such that all but one Sylvester matrix is collected into a block structured submatrix. The rich block structure can then be exploited in structured LU and QR factorization algorithms. These algorithms are shown to require significantly less floating point operations compared to standard algorithms, especially if the polynomial degree is high. Several alternative approaches are discussed for the case \(m=1\), including low-rank displacement methods and the transformation to Cauchy-like form. A number of numerical examples is given and the use of efficient methods for symbolic computations is discussed.