Generic Convolution

Asymptotically fast convolution of lists over any commutative ring in which the multiply-by-two map is injective. (More precisely, if \(x \in R\), and \(x = 2^k*y\) for some \(k \geq 0\), we require that \(R(x/2^k)\) returns \(y\).)

The main function to be exported is convolution().

EXAMPLES:

sage: convolution([1, 2, 3, 4, 5], [6, 7])
[6, 19, 32, 45, 58, 35]

>>> from sage.all import *
>>> convolution([Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)], [Integer(6), Integer(7)])
[6, 19, 32, 45, 58, 35]

The convolution function is reasonably fast, even though it is written in pure Python. For example, the following takes less than a second:

sage: v = convolution(list(range(1000)), list(range(1000)))

>>> from sage.all import *
>>> v = convolution(list(range(Integer(1000))), list(range(Integer(1000))))

ALGORITHM:

Converts the problem to multiplication in the ring \(S[x]/(x^M - 1)\), where \(S = R[y]/(y^K + 1)\) (where \(R\) is the original base ring). Performs FFT with respect to the roots of unity \(1, y, y^2, \ldots, y^{2K-1}\) in \(S\). The FFT/IFFT are accomplished with just additions and subtractions and rotating python lists. (I think this algorithm is essentially due to Schonhage, not completely sure.) The pointwise multiplications are handled recursively, switching to a classical algorithm at some point.

Complexity is O(n log(n) log(log(n))) additions/subtractions in R and O(n log(n)) multiplications in R.

AUTHORS:

  • David Harvey (2007-07): first implementation

  • William Stein: editing the docstrings for inclusion in Sage.

sage.rings.polynomial.convolution.convolution(L1, L2)[source]

Return convolution of non-empty lists L1 and L2.

L1 and L2 may have arbitrary lengths.

EXAMPLES:

sage: convolution([1, 2, 3], [4, 5, 6, 7])
[4, 13, 28, 34, 32, 21]

>>> from sage.all import *
>>> convolution([Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5), Integer(6), Integer(7)])
[4, 13, 28, 34, 32, 21]