AlgorithmAlgorithm: AI-adaptedProof: Not applicablePipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Exact Cauchy matrix-vector product on a radix-two root grid

Definition

Input an integer $M = 2^{q}$ with $q \geq 0$ , a primitive $M$ th root of unity $ω$ , a finite list of poles $μ_{1}, \dots, μ_{n} \in C$ , and weights $a_{1}, \dots, a_{n} \in C$ . The required output is $y_{k} = \sum_{j = 1}^{n} a_{j} / (ω^{k} - μ_{j})$ for $0 \leq k < M$ , provided no denominator is zero. If $n = 0$ , return the zero vector.

Here a primitive $M$ th root means $ω^{M} = 1$ and $ω^{k} \neq 1$ for $1 \leq k < M$ . For $n \geq 1$ , form a balanced binary tree on the pole indices, splitting each consecutive index interval into two intervals whose sizes differ by at most one. At a leaf containing index $j$ , store polynomials $D_{j} (z) = z - μ_{j}$ and $P_{j} (z) = a_{j}$ . At an internal node with disjoint child index sets $I_{1}, I_{2}$ , store $D_{I} (z) = D_{I_{1}} (z) D_{I_{2}} (z), P_{I} (z) = P_{I_{1}} (z) D_{I_{2}} (z) + D_{I_{1}} (z) P_{I_{2}} (z) .$ At the root, fold the coefficients of each polynomial modulo $z^{M} - 1$ : the coefficient at degree $r$ is replaced by the sum of coefficients at degrees congruent to $r$ modulo $M$ . Let $ω_{0} = e^{- 2 π i / M}$ , which equals $1$ when $M = 1$ . Apply the radix-two DFT procedure to each folded coefficient vector to evaluate $P_{I}$ and $D_{I}$ at $ω_{0}^{j}$ , $0 \leq j < M$ . If $M > 1$ , find the unique odd integer $s \in {1, 3, \dots, M - 1}$ with $ω = ω_{0}^{s}$ by generating and comparing the $M$ powers of $ω_{0}$ , then place the value at index $s k m o d M$ at output index $k$ ; this is the supplied root order because $ω^{k} = ω_{0}^{s k}$ . For $M = 1$ , the only root is $1$ and no reindexing is needed. This root search and reindexing use $O (M)$ operations. If some reindexed $D_{I} (ω^{k}) = 0$ , return status collision; otherwise return $y_{k} = P_{I} (ω^{k}) / D_{I} (ω^{k})$ .

Definition references

Pan, “Fast Approximate Computations with Cauchy Matrices and Polynomials,” §§3.2–3.3

Radix-two discrete Fourier transform

Depends on

Radix-two discrete Fourier transform

Used by

Dependency tree · one level

1 result within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Pan, Fast Approximate Computations with Cauchy Matrices and Polynomials, §§3.2–3.3 (standard reference, not scraped)