FractionFreeFastGaussian(D, V)¶
fffg.spad line 45 [edit on github]
D: Join(IntegralDomain, GcdDomain)
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 ofx^k
inz^l
g
(x
), wherez*
(a+b*x+c*x^2+d*x^3+…) = (a*x+b*x^2+c*x^3+…), i.e. multiplication withx
.
- DiffC: NonNegativeInteger -> List D
DiffC
gives the coefficientsc_
{k
,k
} in the expansion <x^k>z
g
(x
) = sum_{i=0
}^k
c_
{k
,i
} <x^i>g
(x
), wherez
acts ong
(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 ofc_
{i
,i
}. These are the only values ofC
explicitly needed infffg
. The second argumentc
, computesc_k
(M
), i.e.c_k
(.) is the dual basis of the vector spaceV
, but also knows about the special multiplication rule as described in Equation (2). Note that the information aboutf
is therefore encoded inc
.vd
is modified by the routine, on input it is the vector of degree boundsn
, 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 ofx^k
inp
(z
)dotf
(x
), where theaction
ofz^l
on a polynomial inx
is given byaction
, i.e.action
(k
,l
,f
) should return the coefficient ofx^k
inz^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 actionCA
of polynomials on the elements off
. 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 columni
are in this case eta +e
.i
- [1, 1, …, 1], where the degree of zero is-1
. The first argumentC
is the list of coefficientsc_
{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 ofx^k
inz^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 likegeneralInterpolation(C, CA, f, eta)
but solves up to orderK
and modifiesvd
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 listseta
with maximal entrymaxEta
and sum of entries at mostsumEta
.
- interpolate: (List D, List D, NonNegativeInteger) -> Fraction SparseUnivariatePolynomial D
interpolate(xlist, ylist, deg)
returns the rational function with numerator degree at mostdeg
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 degreedeg
that interpolates the given points using fraction free arithmetic.
- qShiftAction: (D, NonNegativeInteger, NonNegativeInteger, V) -> D
qShiftAction(q, k, l, g)
gives the coefficient ofx^k
inz^l
g
(x
), wherez*
(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 coefficientsc_
{k
,k
} in the expansion <x^k>z
g
(x
) = sum_{i=0
}^k
c_
{k
,i
} <x^i>g
(x
), wherez
acts ong
(x
) by shifting. In fact, the result is [1,q
,q^2
, …]
- ShiftAction: (NonNegativeInteger, NonNegativeInteger, V) -> D
ShiftAction(k, l, g)
gives the coefficient ofx^k
inz^l
g
(x
), wherez*(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 coefficientsc_
{k
,k
} in the expansion <x^k>z
g
(x
) = sum_{i=0
}^k
c_
{k
,i
} <x^i>g
(x
), wherez
acts ong
(x
) by shifting. In fact, the result is [0, 1, 2, …]