Documentation
¶
Index ¶
- func BuildPointwiseEvaluation(Pi map[string]Polynomial, E expr.Expr, mu *sync.Mutex) ([]koalabear.Element, error)
- func CosetExtLagrangeNormalToCanonicalWithCache(p ExtPolynomial, cache *DomainCache)
- func CosetExtLagrangeToLagrangeNormal(p ExtPolynomial)
- func CosetExtLagrangeToLagrangeNormalWithCache(p ExtPolynomial, cache *DomainCache)
- func CosetLagrangeNormalToCanonicalWithCache(p Polynomial, cache *DomainCache)
- func CosetLagrangeToLagrangeNormal(p Polynomial)
- func CosetLagrangeToLagrangeNormalWithCache(p Polynomial, cache *DomainCache)
- func Evaluate(p Polynomial, d *fft.Domain, zeta koalabear.Element) koalabear.Element
- func EvaluateAtExt(p Polynomial, d *fft.Domain, zeta ext.E6, fftOpts ...fft.Option) ext.E6
- func EvaluateLagrangeAtExt(p Polynomial, lagrangeZetaCache []ext.E6, shift int) ext.E6
- func EvaluateLagrangeWithWeights(p Polynomial, weights []koalabear.Element) koalabear.Element
- func EvaluateOnExtendedDomainRoot(p Polynomial, d *fft.Domain, bigD *fft.Domain, rootIndex int) koalabear.Element
- func ExtEvaluateAtExt(p ExtPolynomial, d *fft.Domain, zeta ext.E6, fftOpts ...fft.Option) ext.E6
- func ExtEvaluateLagrangeAtExt(p ExtPolynomial, lagrangeZetaCache []ext.E6, shift int) ext.E6
- func ExtEvaluateLagrangeWithWeights(p ExtPolynomial, weights []koalabear.Element) ext.E6
- func ExtEvaluateOnExtendedDomainRoot(p ExtPolynomial, d *fft.Domain, bigD *fft.Domain, rootIndex int) ext.E6
- func LagrangeAtZeta(zeta koalabear.Element, N, i int) koalabear.Element
- func LagrangeAtZetaExt(zeta ext.E6, N, i int) ext.E6
- func LagrangeWeightsOnExtendedDomainRoot(d *fft.Domain, bigD *fft.Domain, rootIndex int) []koalabear.Element
- func LagrangesAtZeta(zeta ext.E6, n int) []ext.E6
- func LinComb(v []koalabear.Element, alpha koalabear.Element) koalabear.Element
- func NextPowerOfTwo(n int) int
- func PowUint64(base koalabear.Element, exp uint64) koalabear.Element
- type DomainCache
- type ExtPolynomial
- func AddExt(P1, P2 ExtPolynomial) (ExtPolynomial, error)
- func BuildGrandProductMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, ...) (ExtPolynomial, error)
- func BuildLogupMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, ...) (ExtPolynomial, error)
- func BuildPointwiseEvaluationMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, ...) (ExtPolynomial, error)
- func ComputeQuotientMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, ...) (ExtPolynomial, error)
- func DeepQuotientExt(p ExtPolynomial, v, z ext.E6, d *fft.Domain) ExtPolynomial
- func EvalMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, ...) (ExtPolynomial, error)
- func MulExt(P1, P2 ExtPolynomial) (ExtPolynomial, error)
- func SubExt(P1, P2 ExtPolynomial) (ExtPolynomial, error)
- type Polynomial
- func BuildGrandProduct(P map[string]Polynomial, E1, E2 expr.Expr, mu *sync.Mutex) (Polynomial, error)
- func BuildLogup(P map[string]Polynomial, E, M expr.Expr, mu *sync.Mutex) (Polynomial, error)
- func BuildMultiplicityPolynomials(Pi map[string]Polynomial, S, T []expr.Expr, mu *sync.Mutex) ([]Polynomial, error)
- func BuildWeightedMultiplicityPolynomial(Pi map[string]Polynomial, selS, S, T []expr.Expr, mu *sync.Mutex) ([]Polynomial, error)
- func ComputeQuotient(Pi map[string]Polynomial, vanishingRelation dag.DAG, N int, ...) (Polynomial, error)
- func DeepQuotient(p Polynomial, v, z koalabear.Element, d *fft.Domain) Polynomial
- func Eval(Pi map[string]Polynomial, vanishingRelation dag.DAG, N int) (Polynomial, error)
- type QuotientConfig
- type QuotientOption
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuildPointwiseEvaluation ¶
func BuildPointwiseEvaluation(Pi map[string]Polynomial, E expr.Expr, mu *sync.Mutex) ([]koalabear.Element, error)
BuildPointwiseEvaluation evaluates E point-wise over Pi and returns the N results as a freshly allocated slice. N is the size of the polynomials in Pi (all must have the same size, except constants which have size 1).
func CosetExtLagrangeNormalToCanonicalWithCache ¶
func CosetExtLagrangeNormalToCanonicalWithCache(p ExtPolynomial, cache *DomainCache)
CosetExtLagrangeNormalToCanonicalWithCache is the ext-field counterpart of CosetLagrangeNormalToCanonicalWithCache.
func CosetExtLagrangeToLagrangeNormal ¶
func CosetExtLagrangeToLagrangeNormal(p ExtPolynomial)
CosetExtLagrangeToLagrangeNormal converts an extension polynomial from coset-Lagrange normal form to standard Lagrange normal form.
func CosetExtLagrangeToLagrangeNormalWithCache ¶
func CosetExtLagrangeToLagrangeNormalWithCache(p ExtPolynomial, cache *DomainCache)
CosetExtLagrangeToLagrangeNormalWithCache converts p in place using cache for the FFT domain.
func CosetLagrangeNormalToCanonicalWithCache ¶
func CosetLagrangeNormalToCanonicalWithCache(p Polynomial, cache *DomainCache)
CosetLagrangeNormalToCanonicalWithCache converts p in place from coset-Lagrange Normal form (evaluations on the coset {FrGen·ω^j}) to canonical Normal form (coefficients c_k in standard order). This is the first half of CosetLagrangeToLagrangeNormalWithCache; callers that subsequently need a different transform (e.g. AIR quotient chunking, which FFTs each N-sized chunk individually) avoid a redundant round-trip FFT.
func CosetLagrangeToLagrangeNormal ¶
func CosetLagrangeToLagrangeNormal(p Polynomial)
CosetLagrangeToLagrangeNormal converts a polynomial from coset-Lagrange Normal form (as returned by ComputeQuotient, evaluated on {FrMultiplicativeGen * ω^j}) to standard Lagrange Normal form (evaluated on {ω^j}). The conversion is in-place.
func CosetLagrangeToLagrangeNormalWithCache ¶
func CosetLagrangeToLagrangeNormalWithCache(p Polynomial, cache *DomainCache)
CosetLagrangeToLagrangeNormalWithCache converts p in place using cache for the FFT domain.
func Evaluate ¶
Evaluate evaluates a polynomial p in Lagrange form at zeta the domain d is assumed to be correctly formed
func EvaluateAtExt ¶
EvaluateAtExt evaluates a base-field polynomial p, stored in Lagrange normal form over d, at the extension-field point zeta. Base coefficients are lifted during Horner evaluation. EvaluateAtExt assumes len(p) is a power of two; behaviour is undefined otherwise. Optional fftOpts are forwarded to the internal FFT (e.g. fft.WithNbTasks(1) when EvaluateAtExt is itself called from inside a parallel.Execute loop).
func EvaluateLagrangeAtExt ¶
EvaluateLagrangeAtExt lagrangeZeta = [L_0(zeta), L_1(zeta), ..., L_n-1(zeta)] (n = power of two), p polynomial in lagrange form, of size n
func EvaluateLagrangeWithWeights ¶
func EvaluateLagrangeWithWeights(p Polynomial, weights []koalabear.Element) koalabear.Element
EvaluateLagrangeWithWeights evaluates a base-field polynomial in Lagrange form using precomputed Lagrange basis weights for the same domain.
func EvaluateOnExtendedDomainRoot ¶
func EvaluateOnExtendedDomainRoot(p Polynomial, d *fft.Domain, bigD *fft.Domain, rootIndex int) koalabear.Element
EvaluateOnExtendedDomainRoot evaluates p, given in Lagrange form over d, at bigD.Generator^rootIndex.
func ExtEvaluateAtExt ¶
ExtEvaluateAtExt evaluates an extension-field polynomial p, stored in Lagrange normal form over d, at the extension-field point zeta.
func ExtEvaluateLagrangeAtExt ¶
ExtEvaluateLagrangeAtExt lagrangeZeta = [L_0(zeta), L_1(zeta), ..., L_n-1(zeta)] (n = power of two), p polynomial in lagrange form, of size n
func ExtEvaluateLagrangeWithWeights ¶
func ExtEvaluateLagrangeWithWeights(p ExtPolynomial, weights []koalabear.Element) ext.E6
ExtEvaluateLagrangeWithWeights is the extension-field counterpart of EvaluateLagrangeWithWeights. The Lagrange weights live in the base field.
func ExtEvaluateOnExtendedDomainRoot ¶
func ExtEvaluateOnExtendedDomainRoot(p ExtPolynomial, d *fft.Domain, bigD *fft.Domain, rootIndex int) ext.E6
ExtEvaluateOnExtendedDomainRoot is the extension-field counterpart of EvaluateOnExtendedDomainRoot.
func LagrangeWeightsOnExtendedDomainRoot ¶
func LagrangeWeightsOnExtendedDomainRoot(d *fft.Domain, bigD *fft.Domain, rootIndex int) []koalabear.Element
LagrangeWeightsOnExtendedDomainRoot returns the evaluations of the Lagrange basis over d at bigD.Generator^rootIndex. It supports the common case where d is a subgroup domain of bigD, but does not rely on that relationship.
func LagrangesAtZeta ¶
LagrangesAtZeta computes [L_0(zeta), L_1(zeta), ..., L_n-1(zeta)] (n = power of two)
func NextPowerOfTwo ¶
NextPowerOfTwo returns the next power of two greater than or equal to n
Types ¶
type DomainCache ¶
type DomainCache struct {
// contains filtered or unexported fields
}
DomainCache memoizes FFT domains by cardinality. Safe for concurrent use.
type ExtPolynomial ¶
ExtPolynomial is a polynomial whose coefficients/evaluations live in the Koalabear E6 extension field.
func AddExt ¶
func AddExt(P1, P2 ExtPolynomial) (ExtPolynomial, error)
AddExt returns the pointwise sum P1 + P2.
func BuildGrandProductMixed ¶
func BuildGrandProductMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, columnFields map[string]field.Kind, E1, E2 expr.Expr, mu *sync.Mutex) (ExtPolynomial, error)
BuildGrandProductMixed returns R such that R[0]=1 and R[i+1]=R[i]*E1(P[i])/E2(P[i]) for mixed base and extension inputs.
func BuildLogupMixed ¶
func BuildLogupMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, columnFields map[string]field.Kind, E, M expr.Expr, mu *sync.Mutex) (ExtPolynomial, error)
BuildLogupMixed returns the running sum M/E for mixed base and extension inputs. The output is always an extension polynomial.
func BuildPointwiseEvaluationMixed ¶
func BuildPointwiseEvaluationMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, columnFields map[string]field.Kind, E expr.Expr, mu *sync.Mutex) (ExtPolynomial, error)
BuildPointwiseEvaluationMixed evaluates E point-wise over mixed base and extension columns and returns E6 values. Base columns stay on the base rail while the DAG evaluator lifts them at extension-valued parents.
func ComputeQuotientMixed ¶
func ComputeQuotientMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, vanishingRelation dag.DAG, N int, opts ...QuotientOption) (ExtPolynomial, error)
ComputeQuotientMixed computes E(Pi)/(X^N-1) for an extension-valued vanishing relation. Base columns stay on the base rail, extension columns stay on the extension rail, and mixed evaluation lifts base values only when an extension node consumes them. The returned quotient is in coset-Lagrange form, matching ComputeQuotient.
func DeepQuotientExt ¶
func DeepQuotientExt(p ExtPolynomial, v, z ext.E6, d *fft.Domain) ExtPolynomial
DeepQuotientExt computes q(X) = (v - p(X)) / (z - X) for an extension-field polynomial p in Lagrange normal form over d. The domain points remain base-field roots of unity and are lifted into E6 for the denominator.
func EvalMixed ¶
func EvalMixed(PiBase map[string]Polynomial, PiExt map[string]ExtPolynomial, vanishingRelation dag.DAG, N int) (ExtPolynomial, error)
EvalMixed evaluates vanishingRelation pointwise on mixed base/extension columns and returns N extension-field results in Lagrange normal form. Base columns referenced from extension-valued nodes are lifted on demand. Used for testing only.
func MulExt ¶
func MulExt(P1, P2 ExtPolynomial) (ExtPolynomial, error)
MulExt returns the pointwise product P1 * P2.
func SubExt ¶
func SubExt(P1, P2 ExtPolynomial) (ExtPolynomial, error)
SubExt returns the pointwise difference P1 - P2.
type Polynomial ¶
Polynomial is a wrapper around EPolynomial that includes additional metadata such as shift.
func BuildGrandProduct ¶
func BuildGrandProduct(P map[string]Polynomial, E1, E2 expr.Expr, mu *sync.Mutex) (Polynomial, error)
BuildGrandProduct returns R such that R[0]=1, R[i+1] = R[i] * E1(P[i]) / E2(P[i]) N = size of the polynomials in P Polynomials in P must have the same basis, same layout
func BuildLogup ¶
func BuildLogup(P map[string]Polynomial, E, M expr.Expr, mu *sync.Mutex) (Polynomial, error)
BuildGrandSum returns R such that R[i] = Σ_{j⩽i}M[j]/E[j] The notation E[i] means the i-th entry of E evaluated on P (same for M).
func BuildMultiplicityPolynomials ¶
func BuildMultiplicityPolynomials(Pi map[string]Polynomial, S, T []expr.Expr, mu *sync.Mutex) ([]Polynomial, error)
BuildMultiplicityPolynomials returns one multiplicity polynomial per target column such that chunks[k][i] = total number of times T[k][i] appears across all source columns S[0], ..., S[len(S)-1].
func BuildWeightedMultiplicityPolynomial ¶
func BuildWeightedMultiplicityPolynomial(Pi map[string]Polynomial, selS, S, T []expr.Expr, mu *sync.Mutex) ([]Polynomial, error)
BuildWeightedMultiplicityPolynomial same as BuildMultiplicityPolynomials, but selectors and target and source are split
func ComputeQuotient ¶
func ComputeQuotient(Pi map[string]Polynomial, vanishingRelation dag.DAG, N int, opts ...QuotientOption) (Polynomial, error)
ComputeQuotient computes E(PI)/X^N-1 /!\ all polynomials must be in normal layout, lagrange basis
func DeepQuotient ¶
func DeepQuotient(p Polynomial, v, z koalabear.Element, d *fft.Domain) Polynomial
DeepQuotient computes q(X) = (v - p(X)) / (z - X) where p is in Lagrange Normal form over domain d and v = p(z) is the claimed evaluation at z outside the domain. Returns q in Lagrange Normal form: q[j] = (v - p(ω^j)) / (z - ω^j). Panics (division by zero) if z happens to be a domain point.
func Eval ¶
func Eval(Pi map[string]Polynomial, vanishingRelation dag.DAG, N int) (Polynomial, error)
Eval evaluates vanishingRelation pointwise on Pi and returns the N results as a Polynomial in Lagrange normal form. All polynomials in Pi must be in Lagrange normal form with the same size N (constants of length 1 are also accepted). Used for testing only
type QuotientConfig ¶
type QuotientConfig struct {
DomainCache *DomainCache
}
QuotientConfig configures quotient computation.
type QuotientOption ¶
type QuotientOption func(c *QuotientConfig) error
QuotientOption configures quotient computation.
func WithDomainCache ¶
func WithDomainCache(cache *DomainCache) QuotientOption
WithDomainCache reuses cache for FFT domains created during quotient computation and coset conversion.
Source Files