Computer algebra, also known as symbolic computation, faces many challenges toward high- performance and practical applications. While some computer algebra systems have made some success, the widespread use of symbolic computing in scientific and engineering applications remains limited. This may be attributed in part to the inherent difficulties of exact computation including expression swell, implementation challenges, and algorithmic complexity. Yet, with the increase in computational power provided by modern computer architectures, efficient implementations are still possible with the right tools and techniques.
To this end, this session is dedicated to exploring high-performance computing applied to computer algebra and its applications, practical and efficient implementations, and research on the challenges inherent to these topics. The scope of this session includes: code optimization techniques; parallel and distributed computing; hardware accelerators (e.g. GPUs); efficient memory management; cache complexity and cache-oblivious algorithms; practical and optimized implementation techniques; and techniques for adaptive or automated performance including auto-tuning and hardware-aware algorithms.
More TBA...
Computing a Groebner basis can be the first step in solving a system of polynomial equations exactly. In this talk, we describe a high performance parallel implementation of the F4 algorithm of Faugere for 63-bit primes. Our implementation in C is available at axcas.net and is released into the public domain, with the goal of seeing it incorporated into computer algebra systems, both commercial and open source, as part of a modular method. Our code implements the matrix compression scheme used by Faugere, which does not duplicate coefficients or monomials and encodes the difference between successive column numbers efficiently using bytes where possible. It uses the parallel probabilistic Gaussian elimination developed by Monagan, Pearce, and Steel, which selects the sparsest pivots, then divides the remaining N rows into blocks of size sqrt(N) and reduces random linear combinations of the rows in each block, stopping when zero reductions start to occur. We have developed a new approach to parallel symbolic preprocessing which proceeds in stages to reduce contention, using a parallel version of Davenport's power of two hash table to create monomials. And we have added a dynamic pairs limit which captures early degree drops and controls the memory use on large problems. We present benchmarks of the program running on various machines, including a 16 core/32 thread 5.4GHz Ryzen 9955HX.
A standard way to deal with expression swell in computer algebra is to use multi-modular or evaluation-interpolation methods. When such computations involve Gröbner bases, these methods typically compute many Gröbner bases of specializations of the same ideal. This can be done efficiently with some precomputation, for instance, using Traverso’s tracing. The package Groebner.jl implements F4 with tracing and provides an accessible interface for it (https://github.com/sumiya11/Groebner.jl). As a result, tracing can be conveniently incorporated into algorithms where computing a Gröbner basis is not the final goal. Additionally, the package supports generic types, allowing SIMD-friendly representations of coefficients (for example, tuples of machine integers) to be compiled into efficient code almost automatically by Julia. In the talk, we will advocate for this design by demonstrating how existing software leverages the tracing from Groebner.jl to achieve order-of-magnitude speedups in several applications, including parameter identifiability of ODEs and polynomial system solving.