A subspace method for the computation of the GCD of polynomials (Q1361353)

Given a set of polynomials \[ Y_i(s)=y_i(0)+\ldots + y_i(d_i)s^{d_i},\quad i=1,\ldots,M, \] the authors present an algorithm to compute a polynomial \(C(s)\) such that \[ Y_i(s)=C(s) H_i(s),\quad i=1,\ldots,M, \] where \(H_i\), \(i=1,\ldots,M,\) have no common roots. The ideas are based on a concept called subspace method and the algorithm can be simply described by well known linear algebra procedures, with the main computation being the null space of an \(M(d+1) \times 2d+1\) matrix, where \(d=\max\{d_1, \ldots , d_M\}\). Heuristics are presented to indicate that the method is robust if data is prone to noise.