Skip to content

Implementation of Toeplitz matricies using several algorithms and SciPy's LinearOperators

License

Notifications You must be signed in to change notification settings

DWesl/py-toeplitz

Repository files navigation

py-toeplitz

Implementation of Toeplitz matricies using several algorithms and SciPy's LinearOperators.

  • Two of the available operators use an implementation that forms a vector of the elements of the first row and column and indexes out the subsets corresponding to the rows as needed.
    • One of these operators uses Cython and SciPy's Cython wrappers for BLAS to speed up the floating-point cases.
  • Another operator uses scipy.signal.convolve.
  • The fourth uses NumPy's FFTs.
  • The fifth uses NumPy stride tricks, which appears to make the array contiguous before doing any products.

All implementations should be lower-memory than scipy.linalg.toeplitz, and the third and fourth implementations also have algorithmic speedups. The first two implementations may be slightly faster due to cache interaction with the smaller memory footprint, but this effect will be small both for matrices small enough to fit entirely in cache and for matrices large enough that even the smaller representation doesn't fit in cache.

Related Software

Performance Comparison

-- implementation
size toeplitz stride_tricks_toeplitz Toeplitz CyToeplitz ConvolveToeplitz FFTToeplitz
8.0 49.7±0μs 140±0μs 395±0μs 571±0μs 430±0μs 582±0μs
16.0 52.1±0μs 80.0±0μs 282±0μs 511±0μs 483±0μs 589±0μs
32.0 53.3±0μs 95.0±0μs 475±0μs 559±0μs 508±0μs 590±0μs
64.0 54.0±0μs 75.0±0μs 420±0μs 380±0μs 354±0μs 411±0μs
128.0 844±0μs 937±0μs 453±0μs 385±0μs 498±0μs 405±0μs
256.0 874±0μs 1.92±0ms 1.26±0ms 406±0μs 392±0μs 437±0μs
512.0 921±0μs 4.01±0ms 2.11±0ms 849±0μs 1.59±0ms 816±0μs
1024.0 1.58±0ms 18.4±0ms 3.01±0ms 943±0μs 1.74±0ms 634±0μs
2048.0 2.55±0ms 38.0±0ms 6.07±0ms 1.64±0ms 2.34±0ms 918±0μs
4096.0 7.29±0ms 152±0ms 10.7±0ms 4.48±0ms 2.98±0ms 148±0ms
8192.0 28.5±0ms 613±0ms 34.0±0ms 18.9±0ms 4.55±0ms 4.48±0ms
16384.0 122±0ms 2.34±0s 620±0ms 489±0ms 12.1±0ms 14.9±0ms

CPython 3.6 with Cython 0.29.5, NumPy 1.16.6, and SciPy 1.2.3. ConvolveToeplitz and FFTToeplitz may be faster with the recent FFT improvements in NumPy.

About

Implementation of Toeplitz matricies using several algorithms and SciPy's LinearOperators

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages