fhelium.experimental.bootstrap.polynomial.blocked

Block-factorized Chebyshev evaluation with a shared binary basis.

ChebyshevBlockPlan

class View source

ChebyshevBlockPlan(polynomial: PolynomialApproximation, baby_step: int, coefficients: tuple[tuple[complex, ...], ...], basis_depths: tuple[tuple[int, int], ...], required_depths: int, inventory: tuple[tuple[str, int], ...])

Coefficient blocks, shared binary nodes and their depth schedule.

coefficients[j][i] multiplies T_i(x) T_(j*m)(x). A baby step of zero denotes the direct low-degree schedule. basis_depths records each node's depth relative to the input, in dependency order.

Attributes

Name	Type	Default/value
polynomial	PolynomialApproximation
baby_step	int
coefficients	tuple[tuple[complex, ...], ...]
basis_depths	tuple[tuple[int, int], ...]
required_depths	int
inventory	tuple[tuple[str, int], ...]

BlockedChebyshevEvaluator

class View source

BlockedChebyshevEvaluator(baby_step: int | None = None, skip_near_zero: float = 0.0)

Evaluate $P(x)=\sum _j{A}_j(x)T_{jm}(x)$ with shared binary nodes.

Descending elimination uses $T_{jm+i}=2T_{jm}{T}_i-T_{jm-i}$ without refitting the polynomial. Giants use the original-coordinate binary recurrence. With baby_step=None, $m$ is the smallest power of two satisfying $m^2\ge \mathrm{deg}P$. The plan determines the actual depth cost; constants and low degrees use the direct binary schedule.

At final depth $f$, babies are restricted to $f-2$ while preserving each actual scale $S_k$. Coefficient plaintext scales $p_k=C/S_k$ are selected so every binary64 product is the common $C$. One block rescale produces $A=C/M_{f-2}$. Giants retain common scale $G$ at $f-1$; nonconstant giant products are summed as CT3 before one relinearization/rescale. The $j=0$ block is multiplied by encoded one at scale $G$. All output terms have actual scale $(AG)/M_{f-1}$. Constants are added after block rescale at scale $A$. $M_d$ is the complete dropped prime-group product.

Input and output are CT2 over Q with the same batch axes. The input domain is preserved when retaining NTT; otherwise output is coefficient form. NTT intermediates follow BootstrapArithmetic.retain_ntt. The approximation's domain remains caller-owned; complex inputs are evaluated as $P(z)$ and are never projected to their real part.

Attributes

Name	Type	Default/value
baby_step	int | None	None
skip_near_zero	float	0.0

plan

method

def plan(polynomial: PolynomialApproximation) -> ChebyshevBlockPlan: ...

Return the shared coefficient, basis, depth and operation plan.

required_depths

method

def required_depths(polynomial: PolynomialApproximation) -> int: ...

Return the depth consumed by this polynomial's selected plan.

operation_inventory

method

def operation_inventory(polynomial: PolynomialApproximation) -> dict[str, int]: ...

Count products, relinearizations and group rescales in the plan.

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...]: ...

Return basis-product depths and the single delayed giant-sum depth.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | EvaluationKeySet | Mapping[int, RelinearizationKey] | None=None) -> Ciphertext: ...

Execute the plan, retaining actual scales and the input domain.