[SciPy-Dev] Efficient Toeplitz Matrix-Vector Multiplication

Tue Jan 21 11:03:22 EST 2020

Hi Aditya,
We do have Convolve1D (https://pylops.readthedocs.io/en/latest/api/generated/pylops.signalprocessing.Convolve1D.html#pylops.signalprocessing.Convolve1D ) which is basically what Toeplitz does in the description of the MIT page you point to in the PR. 

The choice of calling it Convolve1D in first place is that because I personally  like things to be called for what they do (Toeplitz is well know matrix type but Convolve is even more explicative). Our method directly wraps scipy.signal.convolve when applied to 1d signals with the possibility of choosing the method of application (time or freq) and scipy.signal.fftconvolve when applied in batched mode (ie along one direction of a N-d signal). In adjoint mode it’s just applying the same methods with flipped filter. On top of that we also provide Convolve2D and ConvolveND where now the convolution is applied to 2 or more directions. That would effectively become a Blockdiagonal matrix of Toeplitz matrices, one more reason for using Convolve ;)

I think by modifying the input filter appropriately you can get what circulant does as well.

This is not to say that your PR should not be pushed forward. I see that Toeplitz and Circulant are very very popular in many different fields of science, but again I stress that in my personal opinion they should implemented by subclassing LinearOperator instead of pure method - effectively what you do is a linear operator :)

Thanks!
iMR

>> On 21 Jan 2020, at 16:41, Semper Sebastian TU Ilmenau <Sebastian.Semper at tu-ilmenau.de> wrote:
> 
> Hi, 
> 
> 
> 
> as one of the developers of fastmat, I can tell you that we have Circulant, Toeplitz and respective multilevel-Circulant and Toeplitz routines implemented, which use your proposed trick to do a fast matrix-vector multiplication. ;-)
> 
> 
> 
> Cheers
> 
> Seb
> 
>  
> Von: SciPy-Dev <scipy-dev-bounces+sebastian.semper=tu-ilmenau.de at python.org> im Auftrag von Aditya Ravuri <aditya.ravuri at gmail.com>
> Gesendet: Samstag, 18. Januar 2020 18:20:59
> An: scipy-dev at python.org
> Betreff: Re: [SciPy-Dev] Efficient Toeplitz Matrix-Vector Multiplication
>  
> Hi,
> 
> Fastmat and pylops do not have all the toeplitz methods implemented yet (to my knowledge). If it is determined that scipy is not the appropriate place for these functions, I'm happy to contribute there.
> 
> Regards,
> 
> Aditya
> 
> 
>> On Thu, Jan 16, 2020, 5:01 PM <scipy-dev-request at python.org> wrote:
>> Send SciPy-Dev mailing list submissions to
>>         scipy-dev at python.org
>> 
>> To subscribe or unsubscribe via the World Wide Web, visit
>>         https://mail.python.org/mailman/listinfo/scipy-dev
>> or, via email, send a message with subject or body 'help' to
>>         scipy-dev-request at python.org
>> 
>> You can reach the person managing the list at
>>         scipy-dev-owner at python.org
>> 
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of SciPy-Dev digest..."
>> 
>> 
>> Today's Topics:
>> 
>>    1. Re: cuSignal: GPU accelerated version of SciPy Signal package
>>       (Juan Luis Cano)
>>    2. Re: Efficient Toeplitz Matrix-Vector Multiplication
>>       (Semper Sebastian TU Ilmenau)
>> 
>> 
>> ----------------------------------------------------------------------
>> 
>> Message: 1
>> Date: Thu, 16 Jan 2020 15:20:07 +0100
>> From: Juan Luis Cano <juanlu001 at gmail.com>
>> To: SciPy Developers List <scipy-dev at python.org>
>> Subject: Re: [SciPy-Dev] cuSignal: GPU accelerated version of SciPy
>>         Signal package
>> Message-ID:
>>         <CAFmivUWhSKC4kFcoFsE36gxaN9Jg37W9S8HFcdybsyMMUs-JkQ at mail.gmail.com>
>> Content-Type: text/plain; charset="UTF-8"
>> 
>> The question is very broad, so I'm answering very broadly as well: I'm
>> happy that someone is splitting the SciPy sub-packages into separate
>> projects... I could see myself using cusignal (or cuintegrate, or
>> cuoptimize) just because of that, regardless of the GPU stuff.
>> 
>> On 1/16/20, Robert Lucente - Pipeline.Com <rlucente at pipeline.com> wrote:
>> > https://github.com/rapidsai/cusignal
>> >
>> > I was wondering what people thought of cuSignal?
>> >
>> > If the topic is not appropriate for this mailing list, please consider
>> > replying directly to me.
>> >
>> > _______________________________________________
>> > SciPy-Dev mailing list
>> > SciPy-Dev at python.org
>> > https://mail.python.org/mailman/listinfo/scipy-dev
>> >
>> 
>> 
>> -- 
>> Juan Luis Cano
>> 
>> 
>> ------------------------------
>> 
>> Message: 2
>> Date: Thu, 16 Jan 2020 14:28:24 +0000
>> From: Semper Sebastian TU Ilmenau <Sebastian.Semper at tu-ilmenau.de>
>> To: SciPy Developers List <scipy-dev at python.org>
>> Subject: Re: [SciPy-Dev] Efficient Toeplitz Matrix-Vector
>>         Multiplication
>> Message-ID: <f1ba5b7e6eae42af9b9e7047b16aea4d at tu-ilmenau.de>
>> Content-Type: text/plain; charset="utf-8"
>> 
>> You could just use
>> 
>> 
>> https://fastmat.readthedocs.io/en/latest/
>> 
>> 
>> or
>> 
>> 
>> https://github.com/equinor/pylops
>> 
>> 
>> for efficient matrix-vector multiplications. ?
>> 
>> ________________________________
>> Von: SciPy-Dev <scipy-dev-bounces+sebastian.semper=tu-ilmenau.de at python.org> im Auftrag von Aditya Ravuri <aditya.ravuri at gmail.com>
>> Gesendet: Montag, 13. Januar 2020 23:01:22
>> An: scipy-dev at python.org
>> Betreff: Re: [SciPy-Dev] Efficient Toeplitz Matrix-Vector Multiplication
>> 
>> Hello,
>> 
>> I've submit a draft PR for this on GitHub: https://github.com/scipy/scipy/pull/11346
>> 
>> An issue has been raised there that adding more functions increases the number of public functions, which is undesirable. If this mailing list can confirm that SciPy will never support matrix methods for special matrices over and above what's already implemented, I will move these lines to the documentation for scipy.linalg.toeplitz as suggested.
>> 
>> Regards,
>> 
>> Aditya
>> 
>> 
>> 
>> On Fri, Jan 10, 2020 at 12:40 AM Aditya Ravuri <aditya.ravuri at gmail.com<mailto:aditya.ravuri at gmail.com>> wrote:
>> Hello,
>> 
>> I'd like to add a function that performs efficient matrix-vector multiplication of Toeplitz matrices with vectors using the circulant matrix embedding trick. A simple example is attached.
>> 
>> May I proceed with coding up an implementation for SciPy based on this script? Is it something that could be added?
>> 
>> An example application of this is in statistics, where stationary processes have a Toeplitz covariance matrix. The efficient matrix vector product can be used to compute log probabilities quickly and perhaps even make use of conjugate gradient solvers in multivariate normals conditional distributions.
>> 
>> Regards,
>> 
>> Aditya
>> 
>> 
>> --
>> AdityaR
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200116/d12d20f8/attachment-0001.html>
>> 
>> ------------------------------
>> 
>> Subject: Digest Footer
>> 
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>> 
>> 
>> ------------------------------
>> 
>> End of SciPy-Dev Digest, Vol 195, Issue 14
>> ******************************************
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200121/27972a89/attachment-0001.html>