FractionFreeFastGaussian(D, V)

fffg.spad line 45 [edit on github]

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

genVectorStream2 is 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, …]