Algebra Commons^™

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

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 …

Metafork: A Compilation Framework For Concurrency Models Targeting Hardware Accelerators, Xiaohui Chen

Electronic Thesis and Dissertation Repository

Parallel programming is gaining ground in various domains due to the tremendous computational power that it brings; however, it also requires a substantial code crafting effort to achieve performance improvement. Unfortunately, in most cases, performance tuning has to be accomplished manually by programmers. We argue that automated tuning is necessary due to the combination of the following factors. First, code optimization is machine-dependent. That is, optimization preferred on one machine may be not suitable for another machine. Second, as the possible optimization search space increases, manually finding an optimized configuration is hard. Therefore, developing new compiler techniques for optimizing applications …

Algorithms To Compute Characteristic Classes, Martin Helmer

Electronic Thesis and Dissertation Repository

In this thesis we develop several new algorithms to compute characteristics classes in a variety of settings. In addition to algorithms for the computation of the Euler characteristic, a classical topological invariant, we also give algorithms to compute the Segre class and Chern-Schwartz-MacPherson (CSM) class. These invariants can in turn be used to compute other common invariants such as the Chern-Fulton class (or the Chern class in smooth cases).

We begin with subschemes of a projective space over an algebraically closed field of characteristic zero. In this setting we give effective algorithms to compute the CSM class, Segre class and …