Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Computer Sciences
High Performance Sparse Multivariate Polynomials: Fundamental Data Structures And Algorithms, Alex Brandt
High Performance Sparse Multivariate Polynomials: Fundamental Data Structures And Algorithms, Alex Brandt
Electronic Thesis and Dissertation Repository
Polynomials may be represented sparsely in an effort to conserve memory usage and provide a succinct and natural representation. Moreover, polynomials which are themselves sparse – have very few non-zero terms – will have wasted memory and computation time if represented, and operated on, densely. This waste is exacerbated as the number of variables increases. We provide practical implementations of sparse multivariate data structures focused on data locality and cache complexity. We look to develop high-performance algorithms and implementations of fundamental polynomial operations, using these sparse data structures, such as arithmetic (addition, subtraction, multiplication, and division) and interpolation. We revisit …
Putting Fürer's Algorithm Into Practice With The Bpas Library, Linxiao Wang
Putting Fürer's Algorithm Into Practice With The Bpas Library, Linxiao Wang
Electronic Thesis and Dissertation Repository
Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as other disciplines. In 1971, Schönhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most n bits to O(log n log log n). In 2007, Martin Fürer presented a new algorithm that runs in O (n log n · 2 ^O(log* n)) , where log*n is the iterated logarithm of n. We explain how we can put Fürer’s ideas into practice for multiplying polynomials over a prime field Z/pZ, which characteristic is a Generalized Fermat prime of …