# FractionFreeFastGaussian(D, V)ΒΆ

- D: Join(IntegralDomain, GcdDomain)
- V: AbelianMonoidRing(D, NonNegativeInteger)

This package implements the interpolation algorithm proposed in Beckermann, Bernhard and Labahn, George, Fraction-free computation of matrix rational interpolants and matrix GCDs, SIAM Journal on Matrix Analysis and Applications 22.

- DiffAction: (NonNegativeInteger, NonNegativeInteger, V) -> D
`DiffAction(k, l, g)`

gives the coefficient of`x^k`

in`z^l`

`g`

(`x`

), where`z*`

(a+b*x+c*x^2+d*x^3+...) = (a*x+b*x^2+c*x^3+...), i.e. multiplication with`x`

.

- DiffC: NonNegativeInteger -> List D
`DiffC`

gives the coefficients`c_`

{`k`

,`k`

} in the expansion <x^k>`z`

`g`

(`x`

) = sum_{`i=0`

}`^k`

`c_`

{`k`

,`i`

} <x^i>`g`

(`x`

), where`z`

acts on`g`

(`x`

) by shifting. In fact, the result is [0, 0, 0, ...]

- fffg: (List D, (NonNegativeInteger, Vector SparseUnivariatePolynomial D) -> D, List NonNegativeInteger) -> Matrix SparseUnivariatePolynomial D
`fffg(C, c, eta)`

is version of fffg which uses sum of eta as order

- fffg: (List D, (NonNegativeInteger, Vector SparseUnivariatePolynomial D) -> D, Vector Integer, NonNegativeInteger) -> Matrix SparseUnivariatePolynomial D
`fffg(C, c, vd, K)`

is the general algorithm as proposed by Beckermann and Labahn. The first argument is the list of`c_`

{`i`

,`i`

}. These are the only values of`C`

explicitely needed in`fffg`

. The second argument`c`

, computes`c_k`

(`M`

), i.e.`c_k`

(.) is the dual basis of the vector space`V`

, but also knows about the special multiplication rule as descibed in Equation (2). Note that the information about`f`

is therefore encoded in`c`

.`vd`

is modified by the routine, on input it is the vector of degree bounds`n`

, as introduced in Definition 2.1. On output it is vector of defects (degree bound minus degree of solution).`K`

is requested order of solution.

- generalCoefficient: ((NonNegativeInteger, NonNegativeInteger, V) -> D, Vector V, NonNegativeInteger, Vector SparseUnivariatePolynomial D) -> D
`generalCoefficient(action, f, k, p)`

gives the coefficient of`x^k`

in`p`

(`z`

)dot`f`

(`x`

), where the`action`

of`z^l`

on a polynomial in`x`

is given by`action`

, i.e.`action`

(`k`

,`l`

,`f`

) should return the coefficient of`x^k`

in`z^l`

`f`

(`x`

).

- generalInterpolation: (List D, (NonNegativeInteger, NonNegativeInteger, V) -> D, Vector V, List NonNegativeInteger) -> Matrix SparseUnivariatePolynomial D
`generalInterpolation(C, CA, f, eta)`

performs Hermite-Pade approximation using the given action`CA`

of polynomials on the elements of`f`

. The result is guaranteed to be correct up to order |eta|-1. Given that eta is a “normal” point, the degrees on the diagonal are given by eta. The degrees of column`i`

are in this case eta +`e`

.`i`

- [1, 1, ..., 1], where the degree of zero is`-1`

. The first argument`C`

is the list of coefficients`c_`

{`k`

,`k`

} in the expansion <x^k>`z`

`g`

(`x`

) = sum_{`i=0`

}`^k`

`c_`

{`k`

,`i`

} <x^i>`g`

(`x`

). The second argument,`CA`

(`k`

,`l`

,`f`

), should return the coefficient of`x^k`

in`z^l`

`f`

(`x`

).

- generalInterpolation: (List D, (NonNegativeInteger, NonNegativeInteger, V) -> D, Vector V, Vector Integer, NonNegativeInteger) -> Matrix SparseUnivariatePolynomial D
`generalInterpolation(C, CA, f, vd, K)`

is like`generalInterpolation(C, CA, f, eta)`

but solves up to order`K`

and modifies`vd`

to return defects of solutions

- genVectorStream2: (NonNegativeInteger, NonNegativeInteger, NonNegativeInteger) -> Stream List NonNegativeInteger
- like genVectorStream, but skips every second vector.

- genVectorStream: (NonNegativeInteger, NonNegativeInteger, NonNegativeInteger) -> Stream List NonNegativeInteger
`genVectorStream(sumEta, maxEta, k)`

generates stream of all possible non-increasing lists`eta`

with maximal entry`maxEta`

and sum of entries at most`sumEta`

.

- interpolate: (List D, List D, NonNegativeInteger) -> Fraction SparseUnivariatePolynomial D
`interpolate(xlist, ylist, deg)`

returns the rational function with numerator degree at most`deg`

and denominator degree at most`\#xlist-deg-1`

that interpolates the given points using fraction free arithmetic. Note that rational interpolation does not guarantee that all given points are interpolated correctly: unattainable points may make this impossible.

- interpolate: (List Fraction D, List Fraction D, NonNegativeInteger) -> Fraction SparseUnivariatePolynomial D
`interpolate(xlist, ylist, deg)`

returns the rational function with numerator degree`deg`

that interpolates the given points using fraction free arithmetic.

- qShiftAction: (D, NonNegativeInteger, NonNegativeInteger, V) -> D
`qShiftAction(q, k, l, g)`

gives the coefficient of`x^k`

in`z^l`

`g`

(`x`

), where`z*`

(a+b*x+c*x^2+d*x^3+...) = (a+q*b*x+q^2*c*x^2+q^3*d*x^3+...). In terms of sequences, z*u(`n`

)=q^n*u(`n`

).

- qShiftC: (D, NonNegativeInteger) -> List D
`qShiftC`

gives the coefficients`c_`

{`k`

,`k`

} in the expansion <x^k>`z`

`g`

(`x`

) = sum_{`i=0`

}`^k`

`c_`

{`k`

,`i`

} <x^i>`g`

(`x`

), where`z`

acts on`g`

(`x`

) by shifting. In fact, the result is [1,`q`

,`q^2`

, ...]

- ShiftAction: (NonNegativeInteger, NonNegativeInteger, V) -> D
`ShiftAction(k, l, g)`

gives the coefficient of`x^k`

in`z^l`

`g`

(`x`

), where`z*(a+b*x+c*x^2+d*x^3+...) = (b*x+2*c*x^2+3*d*x^3+...)`

. In terms of sequences, z*u(`n`

)=n*u(`n`

).

- ShiftC: NonNegativeInteger -> List D
`ShiftC`

gives the coefficients`c_`

{`k`

,`k`

} in the expansion <x^k>`z`

`g`

(`x`

) = sum_{`i=0`

}`^k`

`c_`

{`k`

,`i`

} <x^i>`g`

(`x`

), where`z`

acts on`g`

(`x`

) by shifting. In fact, the result is [0, 1, 2, ...]