issymmetric/ishermitian for Circulant

[jishnub]

These may be computed in O(n) instead of the fallback O(n^2)

[codecov]

Codecov Report

Patch coverage: 96.03% and project coverage change: +0.10 🎉

Comparison is base (49bde1d) 94.98% compared to head (b3ae217) 95.08%.

Additional details and impacted files

@@            Coverage Diff             @@
##           master      #95      +/-   ##
==========================================
+ Coverage   94.98%   95.08%   +0.10%     
==========================================
  Files           7        8       +1     
  Lines         798      896      +98     
==========================================
+ Hits          758      852      +94     
- Misses         40       44       +4     

Impacted Files	Coverage Δ
src/ToeplitzMatrices.jl	87.50% <81.81%> (-4.81%)	⬇️
src/eigen.jl	96.92% <96.92%> (ø)
src/hankel.jl	96.20% <100.00%> (+0.04%)	⬆️
src/linearalgebra.jl	92.69% <100.00%> (+0.30%)	⬆️
src/special.jl	99.33% <100.00%> (+0.03%)	⬆️
src/toeplitz.jl	97.56% <100.00%> (+0.03%)	⬆️

☔ View full report in Codecov by Sentry.
📢 Do you have feedback about the report comment? Let us know in this issue.

[putianyi889]

Why is the first entry special? LinearAlgebra doesn't tackle the first entry separately.

[jishnub]

The first entry corresponds to the principal diagonal. LinearAlgebra checks all elements, so it doesn't need to have special checks for the diagonal. One approach here could be C.vr == vec(adjoint(C.vc)), but since C.vr allocates currently, it's perhaps better to not use this. Separating out the principal diagonal makes the check easier, as that's how _circulate is defined. How would you suggest doing it?

[putianyi889]

I'm thinking of rewritting _circulate and _firstnonzero so that they don't allocate. Then issymmetric and ishermitian can cover AbstractToeplitz.

[jishnub]

One way to rewrite _circulate could be to take on https://github.com/Vexatos/CircularArrays.jl as a dependency, so that

julia> ToeplitzMatrices._circulate(1:4)
4-element Vector{Int64}:
 1
 4
 3
 2

julia> view(CircularVector(1:4), 1:-1:-2)
4-element view(CircularVector(::UnitRange{Int64}), 1:-1:-2) with eltype Int64:
 1
 4
 3
 2

_firstnonzero could be a OneElement from FillArrays

[putianyi889]

using view(A, 1, :) or view(A, :, 1) could also work. OneElement has a risk which is when you convert TriangularToeplitz to Toeplitz, an argument would stay lazy.

[jishnub]

view(A, 1, :) could be fine, we need to check which variant is the most performant.

OneElement has a risk which is when you convert TriangularToeplitz to Toeplitz, an argument would stay lazy

Is this a problem? Does this break anything, other than setindex! into the properties?

[jishnub]

In any case, this doesn't fundamentally change the O(n) behavior, so I would say that we may go ahead with this PR, and change the implementation of issymmetric when the property access becomes performant.

[putianyi889]

The way view(A, 1, :) works is basically the same as CircularArrays or OneElement as they all have proprietary getindex. A benefit of view is that when you do copy, you get the "desired" type.

[jishnub]

We can certainly start with view, as this doesn't require extra dependencies. If a compelling need arises, we may change the implementation later