Skip to main content

The fast transposed Vandermonde solver and its implementation in C

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2024-04-12
Authors/Contributors
Author: Kwon, Hyukho
Abstract
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.
Document
Extent
90 pages.
Identifier
etd23012
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Monagan, Michael
Language
English
Member of collection
Download file Size
etd23012.pdf 743.51 KB

Views & downloads - as of June 2023

Views: 28
Downloads: 2