# FractionFreeFastGaussian(D, V)¶

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` explicitly 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 described 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, …]