Efficient reducing functions (maximum, sum, etc.)

[kshedden]

It seems that currently the package iterates over the full matrix rather than exploiting the Toeplitz structure.

[dlfivefifty]

We'd be happy to merge a PR that fixes this

[putianyi889]

mapreduce would be the one to implement

[dlfivefifty]

I don’t think mapreduce is really possible: consider mapreduce(identity, max, A) vs mapreduce(identity, +,A). I don’t think there’s a way to optimise both for toeplitz

[putianyi889]

Technically it's partially possible once #86 is merged: for commutative operations and mapreduce without the dim argument, do mapreduce on all diagonals that are Fills (assuming FillArrays.jl has that implemented), then do mapreduce again on the results. sum would need to work like this while maximum could be easier to do.

Anyway, maximum and sum with a dim argument are not trivial. Circulant has shortcuts, otherwise there need to be some special algorithms.

[putianyi889]

Example:

for op in (:+, :max)
    @eval mapreduce(f, ::typeof($op), A::AbstractToeplitz) = mapreduce(identity, $op, [mapreduce(f, $op, diag(A, k)) for k in -size(A,1)+1:size(A,2)-1])
end

Note that there is an allocation which might be avoided by using a generator/lazy array. This only works after #86 and JuliaArrays/FillArrays.jl#301