Multidimensional complex DFT (Harvey–van der Hoeven §2.4)
DefinitionIntMul_HvdH_Tensorcomplexity-theoryinteger-multiplication
An element of is a -dimensional array , indexed by (so, as in §2.4 of the paper, an index is always read modulo ). TIdx n is this index set.
dftN n is the normalised multidimensional DFT :
where are the canonical representatives. It is a continuous -linear map; Mathlib's norm on arrays is the supremum norm of §2.3, so operator norms are those of §2.6. For it agrees with dft of IntMul_HvdH_Resampling.
Definition code
import Mathlib
/-!
# Multidimensional complex DFTs of Harvey–van der Hoeven
D. Harvey, J. van der Hoeven, *Integer multiplication in time O(n log n)*,
Ann. of Math. 193 (2021), §2.3–§2.4.
An element of `⊗ᵢ ℂ^{nᵢ}` (`1 ≤ i ≤ d`) is a `d`-dimensional array, i.e. a function on the index
set `∏ᵢ ℤ/nᵢℤ`; as in §2.4, an index `jᵢ` is always read modulo `nᵢ`. Mathlib's norm on such
functions is the supremum norm `‖u‖ = max_j |u_j|` of §2.3, and the norm of a continuous linear
map is the operator norm of §2.6.
-/
namespace IntMul.HvdH
open Complex Real
/-- The index set `∏ᵢ ℤ/nᵢℤ` of a `d`-dimensional array of size `n₁ × ⋯ × n_d`. -/
abbrev TIdx {d : ℕ} (n : Fin d → ℕ) : Type := (i : Fin d) → ZMod (n i)
/-- The multidimensional complex DFT `𝓕_{n₁,…,n_d} = ⊗ᵢ 𝓕_{nᵢ}` (§2.4):
`(𝓕 u)_j = (n₁⋯n_d)⁻¹ ∑_k ∏ᵢ e^{-2πi jᵢkᵢ/nᵢ} u_k`. -/
noncomputable def dftN {d : ℕ} (n : Fin d → ℕ) [∀ i, NeZero (n i)] :
(TIdx n → ℂ) →L[ℂ] (TIdx n → ℂ) :=
LinearMap.toContinuousLinearMap (Matrix.toLin' (Matrix.of fun j k : TIdx n =>
∏ i, (1 / (n i : ℂ)) * exp (-2 * π * I * ((j i).val : ℂ) * ((k i).val : ℂ) / (n i : ℂ))))
end IntMul.HvdH
Source
D. Harvey, J. van der Hoeven, Integer multiplication in time O(n log n), Ann. of Math. 193 (2021), https://doi.org/10.4007/annals.2021.193.2.4 (preprint https://hal.science/hal-02070778v2), §2.3–2.4, pp. 11–13 (multidimensional DFT F_{n1,...,nd}).