Solving Parametric Linear Systems using Sparse Rational Function Interpolation.

Ayoola Jinadu, Department of Mathematics, Simon Fraser Univeristy

Thursday August 17th, 10:30am, in AQ 5004.

Abstract:

Let Ax = b be a parametric linear system where the entries of the matrix A and vector b are polynomials in m parameters with integer coefficients and A be of full rank n. The solutions x_i will be rational functions in the parameters. We present a new algorithm for computing x that uses our sparse rational function interpolation which was presented at CASC 2022. It modifies Cuyt and Lee’s sparse rational function interpolation algorithm to use a Kronecker substitution on the parameters. A failure probability analysis and complexity analysis for our new algorithm is presented. We have implemented our algorithm in Maple and C. We present timing results comparing our implementation with a Maple implementation of Bareiss/Edmonds/Lipson fraction free Gaussian elimination and three other algorithms in Maple for solving Ax = b.