Discrete Module¶
The discrete
module in SymPy implements methods to compute discrete
transforms and convolutions of finite sequences.
This module contains functions which operate on discrete sequences.
 Transforms 
fft
,ifft
,ntt
,intt
,fwht
,ifwht
, mobius_transform
,inverse_mobius_transform
 Convolutions 
convolution
,convolution_fft
,convolution_ntt
, convolution_fwht
,convolution_subset
,covering_product
,intersecting_product
Since the discrete transforms can be used to reduce the computational complexity
of the discrete convolutions, the convolutions
module makes use of the
transforms
module for efficient computation (notable for long input sequences).
Transforms¶
This section lists the methods which implement the basic transforms for discrete sequences.
Fast Fourier Transform¶

sympy.discrete.transforms.
fft
(seq, dps=None)[source]¶ Performs the Discrete Fourier Transform (DFT) in the complex domain.
The sequence is automatically padded to the right with zeros, as the radix2 FFT requires the number of sample points to be a power of 2.
This method should be used with default arguments only for short sequences as the complexity of expressions increases with the size of the sequence.
Parameters: seq : iterable
The sequence on which DFT is to be applied.
dps : Integer
Specifies the number of decimal digits for precision.
Examples
>>> from sympy import fft, ifft
>>> fft([1, 2, 3, 4]) [10, 2  2*I, 2, 2 + 2*I] >>> ifft(_) [1, 2, 3, 4]
>>> ifft([1, 2, 3, 4]) [5/2, 1/2 + I/2, 1/2, 1/2  I/2] >>> fft(_) [1, 2, 3, 4]
>>> ifft([1, 7, 3, 4], dps=15) [3.75, 0.5  0.75*I, 1.75, 0.5 + 0.75*I] >>> fft(_) [1.0, 7.0, 3.0, 4.0]
References
[R109] https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm [R110] http://mathworld.wolfram.com/FastFourierTransform.html

sympy.discrete.transforms.
ifft
(seq, dps=None)[source]¶ Performs the Discrete Fourier Transform (DFT) in the complex domain.
The sequence is automatically padded to the right with zeros, as the radix2 FFT requires the number of sample points to be a power of 2.
This method should be used with default arguments only for short sequences as the complexity of expressions increases with the size of the sequence.
Parameters: seq : iterable
The sequence on which DFT is to be applied.
dps : Integer
Specifies the number of decimal digits for precision.
Examples
>>> from sympy import fft, ifft
>>> fft([1, 2, 3, 4]) [10, 2  2*I, 2, 2 + 2*I] >>> ifft(_) [1, 2, 3, 4]
>>> ifft([1, 2, 3, 4]) [5/2, 1/2 + I/2, 1/2, 1/2  I/2] >>> fft(_) [1, 2, 3, 4]
>>> ifft([1, 7, 3, 4], dps=15) [3.75, 0.5  0.75*I, 1.75, 0.5 + 0.75*I] >>> fft(_) [1.0, 7.0, 3.0, 4.0]
References
[R111] https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm [R112] http://mathworld.wolfram.com/FastFourierTransform.html
Number Theoretic Transform¶

sympy.discrete.transforms.
ntt
(seq, prime)[source]¶ Performs the Number Theoretic Transform (NTT), which specializes the Discrete Fourier Transform (DFT) over quotient ring \(Z/pZ\) for prime \(p\) instead of complex numbers \(C\).
The sequence is automatically padded to the right with zeros, as the radix2 NTT requires the number of sample points to be a power of 2.
Parameters: seq : iterable
The sequence on which DFT is to be applied.
prime : Integer
Prime modulus of the form \((m 2^k + 1)\) to be used for performing NTT on the sequence.
Examples
>>> from sympy import ntt, intt >>> ntt([1, 2, 3, 4], prime=3*2**8 + 1) [10, 643, 767, 122] >>> intt(_, 3*2**8 + 1) [1, 2, 3, 4] >>> intt([1, 2, 3, 4], prime=3*2**8 + 1) [387, 415, 384, 353] >>> ntt(_, prime=3*2**8 + 1) [1, 2, 3, 4]
References
[R113] http://www.apfloat.org/ntt.html [R114] http://mathworld.wolfram.com/NumberTheoreticTransform.html [R115] https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29

sympy.discrete.transforms.
intt
(seq, prime)[source]¶ Performs the Number Theoretic Transform (NTT), which specializes the Discrete Fourier Transform (DFT) over quotient ring \(Z/pZ\) for prime \(p\) instead of complex numbers \(C\).
The sequence is automatically padded to the right with zeros, as the radix2 NTT requires the number of sample points to be a power of 2.
Parameters: seq : iterable
The sequence on which DFT is to be applied.
prime : Integer
Prime modulus of the form \((m 2^k + 1)\) to be used for performing NTT on the sequence.
Examples
>>> from sympy import ntt, intt >>> ntt([1, 2, 3, 4], prime=3*2**8 + 1) [10, 643, 767, 122] >>> intt(_, 3*2**8 + 1) [1, 2, 3, 4] >>> intt([1, 2, 3, 4], prime=3*2**8 + 1) [387, 415, 384, 353] >>> ntt(_, prime=3*2**8 + 1) [1, 2, 3, 4]
References
[R116] http://www.apfloat.org/ntt.html [R117] http://mathworld.wolfram.com/NumberTheoreticTransform.html [R118] https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29
Fast Walsh Hadamard Transform¶

sympy.discrete.transforms.
fwht
(seq)[source]¶ Performs the Walsh Hadamard Transform (WHT), and uses Hadamard ordering for the sequence.
The sequence is automatically padded to the right with zeros, as the radix2 FWHT requires the number of sample points to be a power of 2.
Parameters: seq : iterable
The sequence on which WHT is to be applied.
Examples
>>> from sympy import fwht, ifwht >>> fwht([4, 2, 2, 0, 0, 2, 2, 0]) [8, 0, 8, 0, 8, 8, 0, 0] >>> ifwht(_) [4, 2, 2, 0, 0, 2, 2, 0]
>>> ifwht([19, 1, 11, 9, 7, 13, 15, 5]) [2, 0, 4, 0, 3, 10, 0, 0] >>> fwht(_) [19, 1, 11, 9, 7, 13, 15, 5]
References
[R119] https://en.wikipedia.org/wiki/Hadamard_transform [R120] https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform

sympy.discrete.transforms.
ifwht
(seq)[source]¶ Performs the Walsh Hadamard Transform (WHT), and uses Hadamard ordering for the sequence.
The sequence is automatically padded to the right with zeros, as the radix2 FWHT requires the number of sample points to be a power of 2.
Parameters: seq : iterable
The sequence on which WHT is to be applied.
Examples
>>> from sympy import fwht, ifwht >>> fwht([4, 2, 2, 0, 0, 2, 2, 0]) [8, 0, 8, 0, 8, 8, 0, 0] >>> ifwht(_) [4, 2, 2, 0, 0, 2, 2, 0]
>>> ifwht([19, 1, 11, 9, 7, 13, 15, 5]) [2, 0, 4, 0, 3, 10, 0, 0] >>> fwht(_) [19, 1, 11, 9, 7, 13, 15, 5]
References
[R121] https://en.wikipedia.org/wiki/Hadamard_transform [R122] https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform
Möbius Transform¶

sympy.discrete.transforms.
mobius_transform
(seq, subset=True)[source]¶ Performs the Möbius Transform for subset lattice with indices of sequence as bitmasks.
The indices of each argument, considered as bit strings, correspond to subsets of a finite set.
The sequence is automatically padded to the right with zeros, as the definition of subset/superset based on bitmasks (indices) requires the size of sequence to be a power of 2.
Parameters: seq : iterable
The sequence on which Möbius Transform is to be applied.
subset : bool
Specifies if Möbius Transform is applied by enumerating subsets or supersets of the given set.
Examples
>>> from sympy import symbols >>> from sympy import mobius_transform, inverse_mobius_transform >>> x, y, z = symbols('x y z')
>>> mobius_transform([x, y, z]) [x, x + y, x + z, x + y + z] >>> inverse_mobius_transform(_) [x, y, z, 0]
>>> mobius_transform([x, y, z], subset=False) [x + y + z, y, z, 0] >>> inverse_mobius_transform(_, subset=False) [x, y, z, 0]
>>> mobius_transform([1, 2, 3, 4]) [1, 3, 4, 10] >>> inverse_mobius_transform(_) [1, 2, 3, 4] >>> mobius_transform([1, 2, 3, 4], subset=False) [10, 6, 7, 4] >>> inverse_mobius_transform(_, subset=False) [1, 2, 3, 4]
References
[R123] https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula [R124] https://people.csail.mit.edu/rrw/presentations/subsetconv.pdf [R125] https://arxiv.org/pdf/1211.0189.pdf

sympy.discrete.transforms.
inverse_mobius_transform
(seq, subset=True)[source]¶ Performs the Möbius Transform for subset lattice with indices of sequence as bitmasks.
The indices of each argument, considered as bit strings, correspond to subsets of a finite set.
The sequence is automatically padded to the right with zeros, as the definition of subset/superset based on bitmasks (indices) requires the size of sequence to be a power of 2.
Parameters: seq : iterable
The sequence on which Möbius Transform is to be applied.
subset : bool
Specifies if Möbius Transform is applied by enumerating subsets or supersets of the given set.
Examples
>>> from sympy import symbols >>> from sympy import mobius_transform, inverse_mobius_transform >>> x, y, z = symbols('x y z')
>>> mobius_transform([x, y, z]) [x, x + y, x + z, x + y + z] >>> inverse_mobius_transform(_) [x, y, z, 0]
>>> mobius_transform([x, y, z], subset=False) [x + y + z, y, z, 0] >>> inverse_mobius_transform(_, subset=False) [x, y, z, 0]
>>> mobius_transform([1, 2, 3, 4]) [1, 3, 4, 10] >>> inverse_mobius_transform(_) [1, 2, 3, 4] >>> mobius_transform([1, 2, 3, 4], subset=False) [10, 6, 7, 4] >>> inverse_mobius_transform(_, subset=False) [1, 2, 3, 4]
References
[R126] https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula [R127] https://people.csail.mit.edu/rrw/presentations/subsetconv.pdf [R128] https://arxiv.org/pdf/1211.0189.pdf
Convolutions¶
This section lists the methods which implement the basic convolutions for discrete sequences.
Convolution¶
This is a general method for calculating the convolution of discrete
sequences, which internally calls one of the methods convolution_fft
,
convolution_ntt
, convolution_fwht
, or convolution_subset
.

sympy.discrete.convolutions.
convolution
(a, b, cycle=0, dps=None, prime=None, dyadic=None, subset=None)[source]¶ Performs convolution by determining the type of desired convolution using hints.
Exactly one of
dps
,prime
,dyadic
,subset
arguments should be specified explicitly for identifying the type of convolution, and the argumentcycle
can be specified optionally.For the default arguments, linear convolution is performed using FFT.
Parameters: a, b : iterables
The sequences for which convolution is performed.
cycle : Integer
Specifies the length for doing cyclic convolution.
dps : Integer
Specifies the number of decimal digits for precision for performing FFT on the sequence.
prime : Integer
Prime modulus of the form \((m 2^k + 1)\) to be used for performing NTT on the sequence.
dyadic : bool
Identifies the convolution type as dyadic (bitwiseXOR) convolution, which is performed using FWHT.
subset : bool
Identifies the convolution type as subset convolution.
Examples
>>> from sympy import convolution, symbols, S, I >>> u, v, w, x, y, z = symbols('u v w x y z')
>>> convolution([1 + 2*I, 4 + 3*I], [S(5)/4, 6], dps=3) [1.25 + 2.5*I, 11.0 + 15.8*I, 24.0 + 18.0*I] >>> convolution([1, 2, 3], [4, 5, 6], cycle=3) [31, 31, 28]
>>> convolution([111, 777], [888, 444], prime=19*2**10 + 1) [1283, 19351, 14219] >>> convolution([111, 777], [888, 444], prime=19*2**10 + 1, cycle=2) [15502, 19351]
>>> convolution([u, v], [x, y, z], dyadic=True) [u*x + v*y, u*y + v*x, u*z, v*z] >>> convolution([u, v], [x, y, z], dyadic=True, cycle=2) [u*x + u*z + v*y, u*y + v*x + v*z]
>>> convolution([u, v, w], [x, y, z], subset=True) [u*x, u*y + v*x, u*z + w*x, v*z + w*y] >>> convolution([u, v, w], [x, y, z], subset=True, cycle=3) [u*x + v*z + w*y, u*y + v*x, u*z + w*x]
Convolution using Fast Fourier Transform¶

sympy.discrete.convolutions.
convolution_fft
(a, b, dps=None)[source]¶ Performs linear convolution using Fast Fourier Transform.
Parameters: a, b : iterables
The sequences for which convolution is performed.
dps : Integer
Specifies the number of decimal digits for precision.
Examples
>>> from sympy import S, I >>> from sympy.discrete.convolutions import convolution_fft
>>> convolution_fft([2, 3], [4, 5]) [8, 22, 15] >>> convolution_fft([2, 5], [6, 7, 3]) [12, 44, 41, 15] >>> convolution_fft([1 + 2*I, 4 + 3*I], [S(5)/4, 6]) [5/4 + 5*I/2, 11 + 63*I/4, 24 + 18*I]
References
[R129] https://en.wikipedia.org/wiki/Convolution_theorem [R130] https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29
Convolution using Number Theoretic Transform¶

sympy.discrete.convolutions.
convolution_ntt
(a, b, prime)[source]¶ Performs linear convolution using Number Theoretic Transform.
Parameters: a, b : iterables
The sequences for which convolution is performed.
prime : Integer
Prime modulus of the form \((m 2^k + 1)\) to be used for performing NTT on the sequence.
Examples
>>> from sympy.discrete.convolutions import convolution_ntt >>> convolution_ntt([2, 3], [4, 5], prime=19*2**10 + 1) [8, 22, 15] >>> convolution_ntt([2, 5], [6, 7, 3], prime=19*2**10 + 1) [12, 44, 41, 15] >>> convolution_ntt([333, 555], [222, 666], prime=19*2**10 + 1) [15555, 14219, 19404]
References
[R131] https://en.wikipedia.org/wiki/Convolution_theorem [R132] https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29
Convolution using Fast Walsh Hadamard Transform¶

sympy.discrete.convolutions.
convolution_fwht
(a, b)[source]¶ Performs dyadic (bitwiseXOR) convolution using Fast Walsh Hadamard Transform.
The convolution is automatically padded to the right with zeros, as the radix2 FWHT requires the number of sample points to be a power of 2.
Parameters: a, b : iterables
The sequences for which convolution is performed.
Examples
>>> from sympy import symbols, S, I >>> from sympy.discrete.convolutions import convolution_fwht
>>> u, v, x, y = symbols('u v x y') >>> convolution_fwht([u, v], [x, y]) [u*x + v*y, u*y + v*x]
>>> convolution_fwht([2, 3], [4, 5]) [23, 22] >>> convolution_fwht([2, 5 + 4*I, 7], [6*I, 7, 3 + 4*I]) [56 + 68*I, 10 + 30*I, 6 + 50*I, 48 + 32*I]
>>> convolution_fwht([S(33)/7, S(55)/6, S(7)/4], [S(2)/3, 5]) [2057/42, 1870/63, 7/6, 35/4]
References
[R133] https://www.radioeng.cz/fulltexts/2002/02_03_40_42.pdf [R134] https://en.wikipedia.org/wiki/Hadamard_transform
Subset Convolution¶

sympy.discrete.convolutions.
convolution_subset
(a, b)[source]¶ Performs Subset Convolution of given sequences.
The indices of each argument, considered as bit strings, correspond to subsets of a finite set.
The sequence is automatically padded to the right with zeros, as the definition of subset based on bitmasks (indices) requires the size of sequence to be a power of 2.
Parameters: a, b : iterables
The sequences for which convolution is performed.
Examples
>>> from sympy import symbols, S, I >>> from sympy.discrete.convolutions import convolution_subset >>> u, v, x, y, z = symbols('u v x y z')
>>> convolution_subset([u, v], [x, y]) [u*x, u*y + v*x] >>> convolution_subset([u, v, x], [y, z]) [u*y, u*z + v*y, x*y, x*z]
>>> convolution_subset([1, S(2)/3], [3, 4]) [3, 6] >>> convolution_subset([1, 3, S(5)/7], [7]) [7, 21, 5, 0]
References
[R135] https://people.csail.mit.edu/rrw/presentations/subsetconv.pdf
Covering Product¶

sympy.discrete.convolutions.
covering_product
(a, b)[source]¶ Returns the covering product of given sequences.
The indices of each argument, considered as bit strings, correspond to subsets of a finite set.
The covering product of given sequences is a sequence which contains the sum of products of the elements of the given sequences grouped by the bitwiseOR of the corresponding indices.
The sequence is automatically padded to the right with zeros, as the definition of subset based on bitmasks (indices) requires the size of sequence to be a power of 2.
Parameters: a, b : iterables
The sequences for which covering product is to be obtained.
Examples
>>> from sympy import symbols, S, I, covering_product >>> u, v, x, y, z = symbols('u v x y z')
>>> covering_product([u, v], [x, y]) [u*x, u*y + v*x + v*y] >>> covering_product([u, v, x], [y, z]) [u*y, u*z + v*y + v*z, x*y, x*z]
>>> covering_product([1, S(2)/3], [3, 4 + 5*I]) [3, 26/3 + 25*I/3] >>> covering_product([1, 3, S(5)/7], [7, 8]) [7, 53, 5, 40/7]
References
[R136] https://people.csail.mit.edu/rrw/presentations/subsetconv.pdf
Intersecting Product¶

sympy.discrete.convolutions.
intersecting_product
(a, b)[source]¶ Returns the intersecting product of given sequences.
The indices of each argument, considered as bit strings, correspond to subsets of a finite set.
The intersecting product of given sequences is the sequence which contains the sum of products of the elements of the given sequences grouped by the bitwiseAND of the corresponding indices.
The sequence is automatically padded to the right with zeros, as the definition of subset based on bitmasks (indices) requires the size of sequence to be a power of 2.
Parameters: a, b : iterables
The sequences for which intersecting product is to be obtained.
Examples
>>> from sympy import symbols, S, I, intersecting_product >>> u, v, x, y, z = symbols('u v x y z')
>>> intersecting_product([u, v], [x, y]) [u*x + u*y + v*x, v*y] >>> intersecting_product([u, v, x], [y, z]) [u*y + u*z + v*y + x*y + x*z, v*z, 0, 0]
>>> intersecting_product([1, S(2)/3], [3, 4 + 5*I]) [9 + 5*I, 8/3 + 10*I/3] >>> intersecting_product([1, 3, S(5)/7], [7, 8]) [327/7, 24, 0, 0]
References
[R137] https://people.csail.mit.edu/rrw/presentations/subsetconv.pdf