High-Performance Polynomial Algebra

Adam Strzeboński, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

The upcoming release of Mathematica includes significant performance improvements in polynomial algebra functions and in linear algebra for matrices of univariate polynomials. The release also includes functionality extensions in polynomial algebra over (Subscript[ℤ, p]). The improvements and extensions are based on the FLINT library. In my talk, I will discuss the improvements and show some examples and performance comparison results.

Performance improvements

The FLINT library provides efficient implementations of polynomial algebra algorithms within a fixed polynomial ring. The available rings are univariate polynomials (dense representation) and multivariate polynomials (sparse distributed representation) over the integers, the rationals, and the integers modulo p (separate implementations for machine-sized integers and big integers). The library also provides linear algebra functions for matrices of univariate polynomials over the integers and the integers modulo p for machine-sized p.

Direct improvements

These functions recognize cases that can be handled by FLINT library functions (more efficiently than by the Mathematica internal code) and call FLINT to do the computation.

• PolynomialGCD

• Resultant

• FactorSquareFree

• Factor

• MatrixPower

• Det

• Inverse

• LinearSolve

• RowReduce

• NullSpace

• MatrixRank

Indirect improvements

These functions use the directly improved functions for a large part of their computation or call FLINT functions to do some parts of the computation.

• PolynomialLCM

• Together

• Discriminant

• Subresultants (uses FLINT for the coefficient arithmetic)

• Polynomial real root isolation (uses FLINT Taylor shift implementation)

• All symbolic computation functions use polynomial algebra

Functionality extensions

Factor

Factor now works for multivariate polynomials over (Subscript[ℤ, p]).

Expand[(x+y+x y)(x^2+x y+1),Modulus->2]

Factor[%,Modulus->2]

In Mathematica 13.1:

Factor[x+(x^3)+y+x y+(x^3) y+x (y^2)+(x^2) (y^2),Modulus->2]

Linear algebra

Det, Inverse, LinearSolve, RowReduce, NullSpace, and MatrixRank now work for matrices of univariate rational functions over (Subscript[ℤ, p]) (for machine-sized prime p).

LinearSolve[{{2x+3,x^3-7},{x/(x-1),(x+5)/(x^2-3x+2)}},{x^2+1,x^3+2},Modulus->17]

Together[{{2x+3,x^3-7},{x/(x-1),(x+5)/(x^2-3x+2)}}.%-{x^2+1,x^3+2},Modulus->17]

In Mathematica 13.1:

LinearSolve[{{2x+3,x^3-7},{x/(x-1),(x+5)/(x^2-3x+2)}},{x^2+1,x^3+2},Modulus->17]

Det now works for matrices of multivariate rational functions over (Subscript[ℤ, p]) .

Det[{{x+y,x-y},{x^2-5y,y^2-7x}},Modulus->1009]

In Mathematica 13.1:

Det[{{x+y,x-y},{x^2-5y,y^2-7x}},Modulus->1009]

PolynomialGCD performance improvements

PolynomialGCD[p*r, q*r], with p, q, r randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000.

PolynomialGCD[p*r, q*r], with p, q, r randomly generated bivariate polynomials of total degree n with 10*n terms and 10-bit integer coefficients.

PolynomialGCD[p*r, q*r, Modulus->mod], with p, q, r randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000, and mod=Prime[1234].

PolynomialGCD[p*r, q*r, Modulus->mod], with p, q, r randomly generated bivariate polynomials of total degree n with 10*n terms and 10-bit integer coefficients, and mod=Prime[1234].

Resultant performance improvements

Resultant[p, q, x], with p, q randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000. M marks an out-of-memory abort at 5GB.

Resultant[p, q, y], with p, q randomly generated dense bivariate polynomials of total degree n with integer coefficients between -1000 and 1000.

Resultant[p, q, x, Modulus->mod], with p, q randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000, and mod=Prime[1234].

Resultant[p, q, y, Modulus->mod], with p, q randomly generated dense bivariate polynomials of total degree n with integer coefficients between -1000 and 1000, and mod=Prime[1234].

FactorSquareFree performance improvements

FactorSquareFree[p*q^2], with p, q randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000.

FactorSquareFree[p*q^2], with p, q randomly generated bivariate polynomials of total degree n with 10*n terms and 10-bit integer coefficients.

FactorSquareFree[p*q^2, Modulus->mod], with p, q randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000, and mod=Prime[1234].

FactorSquareFree[p*q^2, Modulus->mod], with p, q randomly generated bivariate polynomials of total degree n with 10*n terms and 10-bit integer coefficients, and mod=Prime[1234].

Factor performance improvements

Factor[p*q], with p, q randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000.

Factor[p*q], with p, q randomly generated trivariate polynomials of total degree n with 10*n terms and 10-bit integer coefficients.

Factor[p*q, Modulus->mod], with p, q randomly generated dense univariate polynomials of degree n with integer coefficients between -1000 and 1000, and mod=Prime[1234].

MatrixPower performance improvements

MatrixPower[m, n], where m is a 10 x 10 matrix of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

Det performance improvements

Det[m], where m is a n x n matrix of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

Inverse performance improvements

Inverse[m], where m is a n x n matrix of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

LinearSolve performance improvements

LinearSolve[m, b], where m is a n x n matrix and b is a n vector of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

RowReduce performance improvements

RowReduce[m], where m is a n x n+3 matrix of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

NullSpace performance improvements

NullSpace[m], where m is a n x n+3 matrix of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

MatrixRank performance improvements

MatrixRank[m], where m is a n x 2n matrix of randomly generated univariate polynomials degree 10 with integer coefficients between -1000 and 1000.

Indirect performance improvements

This benefits from improvements in polynomial factorization and in real root isolation .

SolveValues[ChebyshevT[1000,x]==0,x,Reals]//Length//AbsoluteTiming

In Mathematica 13.1:

SolveValues[ChebyshevT[1000,x]==0,x,Reals]//Length//AbsoluteTiming

Thank you for listening!