Add support for Hermitian Toeplitz matrices ?

[BambOoxX]

Currently there seem to be no specific way to handle Hermitian Toeplitz matrices in Julia.

Using currently available constructors, I managed the small benchmark below

using LinearAlgebra, ToeplitzMatrices, BenchmarkTools
order = 100
col = rand(ComplexF64,order)
col[1] = real(col[1])
Toe = Toeplitz(col,conj(col))
Arr = Matrix(Toe)
Tri = TriangularToeplitz(col,:L)

HerToe = Hermitian(Toe)
HerTri = Hermitian(Tri,:L)
AvgTri = (Tri + Tri' - Diagonal(diag(Tri)))

(Arr == Toe) && (HerToe == Toe) && (HerTri == Toe) && (AvgTri == Toe)

v = rand(order)
@btime $Toe\$v;
@btime $Arr\$v;
@btime $HerToe\$v;
@btime $HerTri\$v;
@btime $AvgTri\$v;

On my system, I get surprisingly worse results using the Toeplitz matrix.

 18.133 ms (18835 allocations: 1.06 MiB)
  98.300 μs (4 allocations: 158.97 KiB)
  110.900 μs (4 allocations: 158.97 KiB)
  105.999 μs (4 allocations: 158.97 KiB)
  100.800 μs (4 allocations: 158.97 KiB)

In the same manner, the least time is spent while computing with the actual dense array. While I am not sure where to start, I would have expected some improvements from the Toeplitz matrix, as well as reduced memory allocation. The Hermitian + TriangularToeplitz combination seem to work quite well however, both in terms of allocations and time, and static memory usage.

In terms of storage, Toeplitz and others represent however an obvious gain as varinfo() returns

name                    size summary 
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
  Arr              156.289 KiB 100×100 Array{Complex{Float64},2}
  AvgTri         156.289 KiB 100×100 Array{Complex{Float64},2}
  HerToe            9.633 KiB 100×100 Hermitian{Complex{Float64},Toeplitz{Complex{Float64},Complex{Float64}}}
  HerTri              8.031 KiB 100×100 Hermitian{Complex{Float64},TriangularToeplitz{Complex{Float64},Complex{Float64}}}
  Toe                 9.617 KiB 100×100 Toeplitz{Complex{Float64},Complex{Float64}}

[dlfivefifty]

PRs will be welcome, though this one will require some thought: Toeplitz precomputes to allow fast multiplication but I doubt this precomputation can be made faster when wrapped in a Hermitian.

My personal preference would be to make Toeplitz lightweight (https://github.com/JuliaMatrices/ToeplitzMatrices.jl/issues/36) and then due the precomputation at the factorization call.

[dlfivefifty]

Note \ using an iterative solver

https://github.com/JuliaMatrices/ToeplitzMatrices.jl/blob/00d7e959f675684eccfe59463a1a3231a897d156/src/ToeplitzMatrices.jl#L249

so its really about fast multiplication. Because of this, I doubt you'll see much improvement for 100 x 100, but it would scale up a lot more than dense.

[BambOoxX]

@dlfivefifty, If I read you posts well, you mean that for such small matrices, using Toeplitz may not be that relevant, can you confirm ?

I just started using Julia, so I guess I am not ready for PRs yet. I will try and see if and how I can contribute.

[dlfivefifty]

You'd be surprised how easy it is to do a PR, assuming you are comfortable with git.

[BambOoxX]

For reference, there are multiple implementations of fast operaions on Toeplitz matrices in the SLICOT library