ISSAC Awards

Citation: Vincent Neiger, Clément Pernet, and Gilles Villard. 2024. Computing Krylov iterates in the time of matrix multiplication. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC '24). Association for Computing Machinery, New York, NY, USA, 419–428. https://doi.org/10.1145/3666000.3669715

Citation: Qiyuan Chen and Ke Ye. 2024. A quasi-optimal lower bound for skew polynomial multiplication. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC '24). Association for Computing Machinery, New York, NY, USA, 74–81. https://doi.org/10.1145/3666000.3669677

Citation: Ido Nahshon and Amir Shpilka. 2024. New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC '24). Association for Computing Machinery, New York, NY, USA, 91–99. https://doi.org/10.1145/3666000.3669679

Citation: Cordian Riener, Robin Schabert, and Thi Xuan Vu. 2024. Connectivity in Symmetric Semi-Algebraic Sets. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC '24). Association for Computing Machinery, New York, NY, USA, 162–169. https://doi.org/10.1145/3666000.3669687

Citation: Manuel Kauers and Jakob Moosbauer. 2023. Flip Graphs for Matrix Multiplication. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC '23). Association for Computing Machinery, New York, NY, USA, 381–388. https://doi.org/10.1145/3597066.3597120

Citation: Marianne Akian, Antoine Béreau, and Stéphane Gaubert. 2023. The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC '23). Association for Computing Machinery, New York, NY, USA, 43–52. https://doi.org/10.1145/3597066.3597089

Citation: Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, and Daniel S. Roche. 2022. Sparse Polynomial Interpolation and Division in Soft-linear Time. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC '22). Association for Computing Machinery, New York, NY, USA, 459–468.

Citation: Barbara Giunti, Guillaume Houry, and Michael Kerber. 2022. Average Complexity of Matrix Reduction for Clique Filtrations. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC '22). Association for Computing Machinery, New York, NY, USA, 187–196.

Citation: The computation of a power series solution of a given ordinary differential equation is a basic problem in computer algebra. For a first-order ordinary differential equation with separation of variables and with p-adic coefficients, the authors of this paper give an optimal bound on the stability of the Newton iteration. The result applies to algorithms for manipulating algebraic numbers over finite fields, for computing isogenies between elliptic curves, and for deterministically finding roots of polynomials in finite fields.

Citation: This paper studies forms of elimination that reveal the dependence structure of matrix rows, columns, or both simultaneously, significantly extending previous work. The authors categorize the forms of elimination including the permutation properties needed in pivot selection and placement to preserve the rank profile properties under various iterative and block approaches. In the course of this, a new strategy emerges to serve as a base case and substantially speed up rank profile preserving tiled elimination. The work is of particular significance because Gaussian elimination and the associated matrix factorization lie at the heart of a great deal of linear algebra, particularly in Computer Algebra.

Citation: The results of this paper are symbolic computation at its best, showing new ways for computers to discover and prove mathematical formulas, studied before for centuries. The paper gives a new algorithmic understanding of a classical problem, finding formulas for the continued fraction expansions of special functions. It is a completely new approach, and it turns insights from experimentation into algorithms, partially heuristic, but with algorithmic proof of correctness. This paper may be a start for a line of new research.

Citation: Multiplying matrices is one of the most fundamental tasks in computational mathematics, it is in the core of most symbolic and numerical algorithms. In 1969 Strassen proved a surprising result improving the exponent in the complexity estimates of square matrix multiplication from the straightforward log_2(8) to log_2(7). Strassen's discovery started an active research area to try to determine the minimal exponent omega.

Francois Le Gall's result is an important contribution to the complexity theory of matrix multiplication, partially because he slightly improves the best known upper-bound for omega.

Le Gall's contribution is twofold: First he gives a concise expression unifying prior approaches to obtain lower-bounds on tensor values. Second, he uses a convex relaxation of the resulting optimization problem, allowing fast computation of its optimum. As a result, he is able to improve the bound on omega in the fifths digit, and designed an efficient method that may used in future analysis and improvements.

Citation: The problem of solving systems of linear equations lies at the heart of exact linear algebra. Storjohann and Yang show a new algorithm for linear system solving over finite fields that is especially fast for systems with low rank. They also show how to apply their algorithm to compute the rank profiles of a matrix. The algorithms are applicable to dense and sparse systems, and automatically take advantage of sparsity when it is present to speed the computation. Their method is based on the use of a novel randomized data structure --- a linear independence oracle --- which is both simple and surprisingly powerful. The paper is part of Shiyun Yang's Master of Mathematics thesis and is primarily her work.

Citation: The Galois theory of linear differential equations with parameters is a very active research area. There is a great deal of theoretical work that has been already developed, but the actual complete algorithms are missing. Dreyfus showed how to compute such a Galois group for a parameterized second order linear differential equation in a special form, under some additional technical conditions. These conditions were later removed by Carlos Arreche, who is also the sole author of the paper that extends these results for all second-order linear differential equations with rational function coefficients. This algorithmic extension is not only original but is also non-trivial.

Citation: A primary goal of the field of computer algebra and symbolic computation is to find new and better ways of computing with mathematical objects. Polynomials are one of the most fundamental objects in computer algebra, and yet a natural sparse representation can present seemingly intractable complexity. More specifically supersparse polynomials are polynomials defined over the rational numbers with relatively few terms whose exponents can be very large integers. While such polynomials have a compact representation as a sum of non-zero terms, some fundamental operations that we take for granted as being easy for ordinary polynomials, such as evaluating at integers, are generally infeasible.

Kaltofen and Koiran extend results of Hendrik Lenstra, Jr. for supersparse polynomials from the univariate to the bivariate case: they exhibit algorithms that can find all linear and quadratic factors of supersparse polynomials in polynomial time. They succeed by fusing classical computer algebra techniques of interpolation and modular reduction with modern randomized methods and deep bounds from algebraic number theory and Diophantine equations.

This work also contributes significantly to our theoretical understanding of algorithms for super-sparse polynomials by analyzing the general complexity of factoring and testing irreducibility. They show that a number of such problems are co-NP-hard, implying for example that a fast algorithm for such a problem would give a fast algorithm for integer factorization.

Citation: Solving systems of polynomial equations stands as one of the great challenges of computer algebra. Rewriting a polynomial in a simpler form using a set of polynomial equations is an important and closely related problem. This paper addresses the challenge of solving a system by developing a better way to simplify a polynomial with respect to that system.

The authors generalize the standard technique of simplification with respect to a monomial term ordering to create a framework of reducing families, reduction operators, and choice functions that leads to a generalized normal form for polynomials. Their generalization of term ordering builds on the Macaulay resultant and holds the potential for better numerical stability properties. They apply this framework to systems of polynomial equations with finitely many solutions where they use conventional numerical linear algebra techniques to compute the solution. The greater freedom in simplification afforded by this framework holds significant promise for improving our ability to solve systems of polynomial equations.

Citation: Solving systems of polynomial equations is a fundamental problem in computational algebraic geometry with applications throughout science and mathematics. Computer scientists seek to quantify how difficult it is to solve a system of equations, however until now, no one has succeeded in bounding the difficulty (or complexity) by anything better than pessimistic exponential bounds, except in a special case where all the coordinates of the solutions are polynomials in one distinguished coordinate (a so-called primitive element).

Dahan and Schost have achieved something remarkable: they broke through the exponential barrier of complexity in the general case and obtained the polynomial bounds that were known previously only in the special case. Reducing a system of polynomial equations to triangular form allows its solutions to be computed more easily. However, the equations in the triangular form might be significantly larger than the original equations, perhaps exponentially larger. They showed that the size of the equations in a triangular form is at worst a quadratic function, and sometimes a linear function (if quotients of polynomials are permitted), of the size of the solution set of the original equations. This breakthrough enhances our understanding of this important problem by showing that the triangular form is in general smaller and less complicated than previously thought and therefore easier to compute and solve. In fact, such a bound directly yields better modular algorithms for computing triangular forms.

Citation: Solving systems of linear equations is the fundamental problem of scientific computation. Over 2000 years ago, an early Chinese book on mathematics described algorithms to solve this problem. In our time, computer simulations of physical processes require solving sparse linear systems with huge numbers of unknowns. Researchers developed specialized algorithms based on methods of Krylov to solve these systems.

More recently, huge sparse systems of linear equations over finite fields have appeared in algorithms for factoring integers or for computing discrete logarithms. Krylov-based algorithms have been generalized to handle these systems. The security of modern cryptographic protocols that secure Internet communications and commerce rest their security partly on the difficulty of solving such linear systems, which increases our need to better understand such computations.

Experiments have suggested that a heuristic modification of Krylov-based algorithms improves performance in practice, but no theoretical analysis has been able to justify the experimental results or to prove the reliability of the heuristic. In his work, Eberly provides for the first time a theoretical justification for the observed experimental results, and he proves that we may rely on randomized Krylov-based algorithms without sacrificing performance. He provides new tight bounds for both the expected amount of look-ahead required when applying a randomized Lanczos algorithm, and the expected length of a sequence of zero-discrepancies that would be encountered when using a simple randomized version of Wiedemann's algorithm.

Citation: Finding roots of polynomials has a long and rich history in scientific computation. In most practical applications, measuring the coefficients of the polynomials involved can lead to errors that affect the accuracy and stability of algorithms that find roots of these polynomials. While we know excellent algorithms for finding single roots, accurately computing multiple roots of polynomials remains a challenge. Using for the first time the pejorative manifold introduced by Kahan, Zeng developed an algorithm that efficiently approximates multiple roots of polynomials, even ones with inexact coefficients, without resorting to slow calculations involving arbitrary precision software floating point numbers. He has also provided an efficient implementation that performs well in experiments, thereby advancing the state of knowledge in this field.

Citation: Solving systems of polynomial equations is a significant challenge that lies at the heart of computer algebra and symbolic computation. Dickenstein and Emiris have made a substantial contribution towards the understanding of formulas, called resultants, that solve systems of polynomial equations efficiently. They have demonstrated how to explicitly compute such formulas in an important special case and have described conditions when such formulas are the best that can be attained. In this special case of multihomogeneous resultants, they have shown how a combinatorial construction can be made intrinsic.

Citation: Since the nineteenth century, mathematicians have studied matrices whose entries are numbers or polynomials in one variable. Both mathematicians and computer scientists are interested in solving equations involving matrices and in finding natural ways to discover the structure of matrices by converting them into certain ``normal forms''. Storjohann has made a substantial contribution towards the development of symbolic matrix algorithms that efficiently solve equations and find normal forms of matrices of polynomials. His method of ``High-Order Lifting'' allows larger, complicated operations to be broken down into smaller steps that rely primarily on the simple yet efficient multiplication of matrices for the bulk of the work. His method improves theoretical estimates and practical performance of algorithms for these two problems as well as other applications.