[ANN] complex algorithms: QR, SVD, FFT

[ktye]

I needed some algorithms on complex matrices, that did not exist yet in go, so I wrote them myself.

Maybe someone finds them useful.

As I'm no expert in the field, I cannot guarantee for their quality:

QR decomposition and solution to overdetermined systems (linear least squares):

https://github.com/ktye/qr

SVD singular value decomposition and computation of matrix conditions:

https://github.com/ktye/svd

FFT fast fourier transform:

https://github.com/ktye/fft

All packages are self-contained. Actually only a single file per package is necessary.

This is something, I have mixed feelings with LAPACK (and gonum).

If you need only a single routine, to build and link lapack always feels a little heavy.

[Daniel Skinner]

Thanks for sharing, FFT is something I've been meaning to dig into and I imagine this will be illuminating.

--
You received this message because you are subscribed to the Google Groups "gonum-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gonum-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Brendan Tracey]

Cool!

FFT will definitely added to gonum at some point. We'd like (full featured) complex matrices as well, but it's an enormous amount of work to get the lapack like algorithms.

Note that Gonum has pure-Go implementations of the Lapack algorithms. The Go compiler automatically does not include functions you don't use, so using the gonum lapack functions doesn't increase the binary size by more than the functions you need.

[Seb Binet]

On Fri, Dec 30, 2016 at 8:31 PM, ktye <kty...@gmail.com> wrote:

I needed some algorithms on complex matrices, that did not exist yet in go, so I wrote them myself.

Maybe someone finds them useful.

As I'm no expert in the field, I cannot guarantee for their quality:

QR decomposition and solution to overdetermined systems (linear least squares):

https://github.com/ktye/qr

SVD singular value decomposition and computation of matrix conditions:

https://github.com/ktye/svd

FFT fast fourier transform:

https://github.com/ktye/fft

great! thanks for sharing.

 

All packages are self-contained. Actually only a single file per package is necessary.

This is something, I have mixed feelings with LAPACK (and gonum).

If you need only a single routine, to build and link lapack always feels a little heavy.

true, but:

1) gonum has pure-go implementations for blas and lapack:

 https://github.com/gonum/blas/blob/master/native/doc.go

 https://github.com/gonum/blas/blob/master/blas64/blas64.go#L13

 https://github.com/gonum/lapack/blob/master/lapack64/lapack64.go#L29

 https://godoc.org/github.com/gonum/lapack/lapack64

(which are used by default, for go-get-ability)

2) you could also have your types implicitly implement the gonum/matrix interfaces, such as cmat128.Matrix and mat64.Matrix:

 https://godoc.org/github.com/gonum/matrix/conv

 https://godoc.org/github.com/gonum/matrix/cmat128

so the gonum ecosystem can be leveraged as a whole and this allows cross-pollinization.

-s

[Dan Kortschak]

Over the past few days I've been working on translating FFTPACK from
netlib - I have an almost working RFFT and will add the CFFT. The PR is
likely to be complex since the FFTPACK algorithm uses Fortran rank 3
tensors. I have mimicked this with some internal types to avoid having
to change this while cleaning out the spaghetti. Some of the Fortran
approach will stay - I won't change the data from column-major since it
is only used internally, but I will clean out the 1-based indexing when
I have the final bugs ironed out.

Where do we want to put it? I have it in gonum.org/v1/gonum/fourier at
this stage, but .../dsp could work as well (I prefer fourier).

[Brendan Tracey]

Why not gonum.org/v1/gonum/fft ?

It’s the name everyone will look for, it’s shorter, and unlikely to clash with anything.

Do we know how good the netlib algorithms are relative to something like fftw?

Thanks for working on this! It’s one of the big pieces we’re missing.

Brendan

[Dan Kortschak]

Because it will be more than just FFT, FFTPACK has other periodic
transforms:

1.   rffti     initialize  rfftf and rfftb
2.   rfftf     forward transform of a real periodic sequence
3.   rfftb     backward transform of a real coefficient array

4.   ezffti    initialize ezfftf and ezfftb
5.   ezfftf    a simplified real periodic forward transform
6.   ezfftb    a simplified real periodic backward transform

7.   sinti     initialize sint
8.   sint      sine transform of a real odd sequence

9.   costi     initialize cost
10.  cost      cosine transform of a real even sequence

11.  sinqi     initialize sinqf and sinqb
12.  sinqf     forward sine transform with odd wave numbers
13.  sinqb     unnormalized inverse of sinqf

14.  cosqi     initialize cosqf and cosqb
15.  cosqf     forward cosine transform with odd wave numbers
16.  cosqb     unnormalized inverse of cosqf

17.  cffti     initialize cfftf and cfftb
18.  cfftf     forward transform of a complex periodic sequence
19.  cfftb     unnormalized inverse of cfftf


"periodic"?

On Sun, 2018-02-04 at 13:34 -0700, Brendan Tracey wrote:
> Why not gonum.org/v1/gonum/fft <http://gonum.org/v1/gonum/fft> ?

[Sebastien Binet]

On Sun, Feb 4, 2018 at 9:42 PM, Dan Kortschak <dan.ko...@adelaide.edu.au> wrote:

Because it will be more than just FFT, FFTPACK has other periodic
transforms:

1.   rffti     initialize  rfftf and rfftb
2.   rfftf     forward transform of a real periodic sequence
3.   rfftb     backward transform of a real coefficient array

4.   ezffti    initialize ezfftf and ezfftb
5.   ezfftf    a simplified real periodic forward transform
6.   ezfftb    a simplified real periodic backward transform

7.   sinti     initialize sint
8.   sint      sine transform of a real odd sequence

9.   costi     initialize cost
10.  cost      cosine transform of a real even sequence

11.  sinqi     initialize sinqf and sinqb
12.  sinqf     forward sine transform with odd wave numbers
13.  sinqb     unnormalized inverse of sinqf

14.  cosqi     initialize cosqf and cosqb
15.  cosqf     forward cosine transform with odd wave numbers
16.  cosqb     unnormalized inverse of cosqf

17.  cffti     initialize cfftf and cfftb
18.  cfftf     forward transform of a complex periodic sequence
19.  cfftb     unnormalized inverse of cfftf


"periodic"?

sounds like Mendeleiv-related :)

I'd prefer "fourier" over "periodic".

-s

[Dan Kortschak]

Yes, it was my understanding this this was the family of operations
this lives in.