Approximant bases and Relation bases for polynomial matrices

[johanrosenkilde]

Approximant bases, or sigma bases, or order bases, are in their original form relaxations of kernel bases of polynomial matrices which behave extremely nicely. They generalise Padé approximation and have many uses in their own right, and they also appear as an important step in many asymptotically fast algorithms that have been developed in recent years.

Relation bases is a more recently studied concept, but a natural generalisation of approximant basis. Mathematically it differs sufficiently to merit a new name.

This ticket introduces an interface for approximant bases and relation basis, and gives rudimentary algorithms for computing them using row reduction of polynomial matrices. The interface is prepared to support faster, specialised algorithms for common cases.

CC: @vneiger

Component: algebra

Keywords: polynomial_matrix

Issue created by migration from https://trac.sagemath.org/ticket/23645

[johanrosenkilde]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
 Approximant bases, or sigma bases, or order bases, are in their original form relaxations of kernel bases of polynomial matrices which behave extremely nicely. They generalise Padé approximation and have many uses in their own right, and they also appear as an important step in many asymptotically fast algorithms that have been developed in recent years.

-This ticket introduces an interface for very general notions of approximant bases, and gives a rudimentary algorithm for computing them using row reduction of polynomial matrices.
+Relation bases is a more recently studied concept, but a natural generalisation of approximant basis. Mathematically it differs sufficiently to merit a new name.
+
+This ticket introduces an interface for approximant bases and relation basis, and gives rudimentary algorithms for computing them using row reduction of polynomial matrices. The interface is prepared to support faster, specialised algorithms for common cases.