离散

SymPy 中的 discrete 模块实现了计算有限序列的离散变换和卷积的方法。

此模块包含对离散序列进行操作的函数。

变换 - fft, ifft, ntt, intt, fwht, ifwht,

mobius_transform，inverse_mobius_transform

卷积 - convolution, convolution_fft, convolution_ntt,

convolution_fwht, convolution_subset, covering_product, intersecting_product

由于离散变换可以用来减少离散卷积的计算复杂度，convolutions 模块利用 transforms 模块进行高效计算（对于长输入序列尤为显著）。

转换

本节列出了实现离散序列基本变换的方法。

快速傅里叶变换

sympy.discrete.transforms.fft(seq, dps=None)[源代码][源代码]

在复数域中执行离散傅里叶变换（DFT）。

序列会自动用零向右填充，因为 radix-2 FFT 要求样本点的数量为2的幂。

此方法应仅在短序列上使用默认参数，因为表达式的复杂性会随着序列大小的增加而增加。

参数:
seq可迭代对象

要应用 DFT 的序列。

dps整数

指定精度的小数位数。

参考文献

[2]

https://mathworld.wolfram.com/快速傅里叶变换.html

示例

>>> 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]
sympy.discrete.transforms.ifft(seq, dps=None)[源代码][源代码]

在复数域中执行离散傅里叶变换（DFT）。

序列会自动用零向右填充，因为 radix-2 FFT 要求样本点的数量为2的幂。

此方法应仅在短序列上使用默认参数，因为表达式的复杂性会随着序列大小的增加而增加。

参数:
seq可迭代对象

要应用 DFT 的序列。

dps整数

指定精度的小数位数。

参考文献

[2]

https://mathworld.wolfram.com/快速傅里叶变换.html

示例

>>> 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]

数论变换

sympy.discrete.transforms.ntt(seq, prime)[源代码][源代码]

执行数论变换（NTT），该变换在质数 \(p\) 的商环 \(Z/pZ\) 上专门化离散傅里叶变换（DFT），而不是在复数 \(C\) 上。

序列会自动用零向右填充，因为 radix-2 NTT 要求样本点的数量为2的幂。

参数:
seq可迭代对象

要应用 DFT 的序列。

质数整数

用于对序列执行 NTT 的形如 \((m 2^k + 1)\) 的素数模数。

参考文献

[3]

https://en.wikipedia.org/wiki/离散傅里叶变换_(一般%29

示例

>>> 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]
sympy.discrete.transforms.intt(seq, prime)[源代码][源代码]

执行数论变换（NTT），该变换在质数 \(p\) 的商环 \(Z/pZ\) 上专门化离散傅里叶变换（DFT），而不是在复数 \(C\) 上。

序列会自动用零向右填充，因为 radix-2 NTT 要求样本点的数量为2的幂。

参数:
seq可迭代对象

要应用 DFT 的序列。

质数整数

用于对序列执行 NTT 的形如 \((m 2^k + 1)\) 的素数模数。

参考文献

[3]

https://en.wikipedia.org/wiki/离散傅里叶变换_(一般%29

示例

>>> 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]

快速沃尔什-哈达玛变换

sympy.discrete.transforms.fwht(seq)[源代码][源代码]

执行 Walsh Hadamard 变换（WHT），并使用 Hadamard 顺序排列序列。

序列会自动用零向右填充，因为 radix-2 FWHT 要求样本点的数量为2的幂。

参数:
seq可迭代对象

要应用WHT的序列。

参考文献

[2]

https://en.wikipedia.org/wiki/快速沃尔什-阿达玛变换

示例

>>> 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]
sympy.discrete.transforms.ifwht(seq)[源代码][源代码]

执行 Walsh Hadamard 变换（WHT），并使用 Hadamard 顺序排列序列。

序列会自动用零向右填充，因为 radix-2 FWHT 要求样本点的数量为2的幂。

参数:
seq可迭代对象

要应用WHT的序列。

参考文献

[2]

https://en.wikipedia.org/wiki/快速沃尔什-阿达玛变换

示例

>>> 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]

Möbius 变换

sympy.discrete.transforms.mobius_transform(seq, subset=True)[源代码][源代码]

对以序列索引为位掩码的子集格执行Möbius变换。

每个参数的索引，被视为位字符串，对应于一个有限集的子集。

序列会自动用零向右填充，因为基于位掩码（索引）的子集/超集定义要求序列的大小为2的幂。

参数:
seq可迭代对象

要应用Mobius变换的序列。

子集布尔

指定是否通过枚举给定集合的子集或超集来应用Mobius变换。

参考文献

示例

>>> 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]
sympy.discrete.transforms.inverse_mobius_transform(seq, subset=True)[源代码][源代码]

对以序列索引为位掩码的子集格执行Möbius变换。

每个参数的索引，被视为位字符串，对应于一个有限集的子集。

序列会自动用零向右填充，因为基于位掩码（索引）的子集/超集定义要求序列的大小为2的幂。

参数:
seq可迭代对象

要应用Mobius变换的序列。

子集布尔

指定是否通过枚举给定集合的子集或超集来应用Mobius变换。

参考文献

示例

>>> 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]

卷积

本节列出了实现离散序列基本卷积的方法。

卷积

这是一种计算离散序列卷积的通用方法，它内部调用以下方法之一：convolution_fft、convolution_ntt、convolution_fwht 或 convolution_subset。

sympy.discrete.convolutions.convolution(
a,
b,
cycle=0,
dps=None,
prime=None,
dyadic=None,
subset=None,
)[源代码][源代码]

通过提示确定所需卷积类型来执行卷积。

必须明确指定 dps、prime、dyadic、subset 参数中的一个，以确定卷积的类型，并且可以选择性地指定 cycle 参数。

对于默认参数，使用 FFT 进行线性卷积。

参数:
a, b可迭代对象

执行卷积的序列。

循环整数

指定进行循环卷积的长度。

dps整数

指定对序列执行 FFT 时的精度小数位数。

质数整数

用于对序列执行 NTT 的形如 \((m 2^k + 1)\) 的素数模数。

二元布尔

将卷积类型标识为二元（按位异或）卷积，该卷积使用 FWHT 进行。

子集布尔

将卷积类型标识为子集卷积。

示例

>>> 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]

使用快速傅里叶变换进行卷积

sympy.discrete.convolutions.convolution_fft(a, b, dps=None)[源代码][源代码]

使用快速傅里叶变换执行线性卷积。

参数:
a, b可迭代对象

执行卷积的序列。

dps整数

指定精度的小数位数。

参考文献

[2]

https://en.wikipedia.org/wiki/离散傅里叶变换_(一般%29

示例

>>> 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]

使用数论变换进行卷积

sympy.discrete.convolutions.convolution_ntt(a, b, prime)[源代码][源代码]

使用数论变换执行线性卷积。

参数:
a, b可迭代对象

执行卷积的序列。

质数整数

用于对序列执行 NTT 的形如 \((m 2^k + 1)\) 的素数模数。

参考文献

[2]

https://en.wikipedia.org/wiki/离散傅里叶变换_(一般%29

示例

>>> 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]

使用快速沃尔什-哈达玛变换进行卷积

sympy.discrete.convolutions.convolution_fwht(a, b)[源代码][源代码]

使用快速沃尔什-哈达玛变换执行双值（按位异或）卷积。

卷积会自动用零向右填充，因为 radix-2 FWHT 要求样本点的数量为2的幂。

参数:
a, b可迭代对象

执行卷积的序列。

参考文献

示例

>>> 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]

子集卷积

sympy.discrete.convolutions.convolution_subset(a, b)[源代码][源代码]

对给定的序列执行子集卷积。

每个参数的索引，被视为位字符串，对应于一个有限集的子集。

序列会自动用零向右填充，因为基于位掩码（索引）的子集定义要求序列的大小为2的幂。

参数:
a, b可迭代对象

执行卷积的序列。

参考文献

示例

>>> from sympy import symbols, S
>>> 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]

产品覆盖

sympy.discrete.convolutions.covering_product(a, b)[源代码][源代码]

返回给定序列的覆盖乘积。

每个参数的索引，被视为位字符串，对应于一个有限集的子集。

给定序列的覆盖产品是一个序列，该序列包含根据相应索引的 按位或 分组的给定序列元素的乘积之和。

序列会自动用零向右填充，因为基于位掩码（索引）的子集定义要求序列的大小为2的幂。

参数:
a, b可迭代对象

需要获取覆盖产品的序列。

参考文献

示例

>>> 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]

交叉产品

sympy.discrete.convolutions.intersecting_product(a, b)[源代码][源代码]

返回给定序列的交集产品。

每个参数的索引，被视为位字符串，对应于一个有限集的子集。

给定序列的交积是包含给定序列元素乘积之和的序列，这些乘积按相应索引的 按位与 分组。

序列会自动用零向右填充，因为基于位掩码（索引）的子集定义要求序列的大小为2的幂。

参数:
a, b可迭代对象

要获取相交乘积的序列。

参考文献

示例

>>> 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]