The fast transposed Vandermonde solver and its implementation in C

We study the algorithm of Kaltofen and Yagati [8], which solves an n × n transposed Vandermonde system of linear equations over a field F . This algorithm does O(n log2 n) arithmetic operations in F. It assumes that the fast Fourier transform (FFT) is used for polynomial multiplication, polynomial division, and polynomial multipoint evaluation over F . We implemented this fast transposed Vandermonde solver in C. It uses the "product tree" of Borodin and Munro [2]. In our C implementation, we optimize the fast multiplication, the fast division, and the fast evaluation algorithms. To speed up fast division, we use Hanrot, Quercia, and Zimmerman's "middle product" [6]. Our fast solver beats Zippel's O(n2) solver [15]when n ≥ 128 and F = Zp with p<263.