Dense * Tridiagonal = Sparse?

[ChrisRackauckas]

julia> using LinearAlgebra

julia> N = 8
8

julia> Mx = Tridiagonal([1.0 for i in 1:N-1],[-2.0 for i in 1:N],[1.0 for i in 1:N-1])
8×8 Tridiagonal{Float64,Array{Float64,1}}:
 -2.0   1.0    ⋅     ⋅     ⋅     ⋅     ⋅     ⋅
  1.0  -2.0   1.0    ⋅     ⋅     ⋅     ⋅     ⋅
   ⋅    1.0  -2.0   1.0    ⋅     ⋅     ⋅     ⋅
   ⋅     ⋅    1.0  -2.0   1.0    ⋅     ⋅     ⋅
   ⋅     ⋅     ⋅    1.0  -2.0   1.0    ⋅     ⋅
   ⋅     ⋅     ⋅     ⋅    1.0  -2.0   1.0    ⋅
   ⋅     ⋅     ⋅     ⋅     ⋅    1.0  -2.0   1.0
   ⋅     ⋅     ⋅     ⋅     ⋅     ⋅    1.0  -2.0

julia> A = rand(N,N)
8×8 Array{Float64,2}:
 0.52234   0.075572   0.492018  0.534107  …  0.11925    0.933859   0.927217
 0.554405  0.674733   0.322482  0.895656     0.025754   0.842152   0.810342
 0.116686  0.603084   0.130214  0.475674     0.0697535  0.97639    0.713087
 0.717719  0.211584   0.568428  0.294381     0.643912   0.270161   0.337518
 0.251835  0.569177   0.554402  0.577696     0.535705   0.854619   0.145042
 0.267439  0.0778166  0.480589  0.133326  …  0.365856   0.543645   0.157496
 0.366063  0.68394    0.365163  0.443594     0.75635    0.0335027  0.0916263
 0.423794  0.728052   0.885349  0.717036     0.24141    0.017163   0.651004

julia> AMx = A*Mx
8×8 SparseArrays.SparseMatrixCSC{Float64,Int64} with 64 stored entries:
  [1, 1]  =  -0.969108
  [2, 1]  =  -0.434078
  [3, 1]  =  0.369713
  [4, 1]  =  -1.22385
  [5, 1]  =  0.0655065
  [6, 1]  =  -0.457062
  [7, 1]  =  -0.0481849
  [8, 1]  =  -0.119537
  [1, 2]  =  0.863215
  [2, 2]  =  -0.472578
  ⋮
  [7, 7]  =  0.780971
  [8, 7]  =  0.858088
  [1, 8]  =  -0.920576
  [2, 8]  =  -0.778531
  [3, 8]  =  -0.449783
  [4, 8]  =  -0.404876
  [5, 8]  =  0.564534
  [6, 8]  =  0.228652
  [7, 8]  =  -0.14975
  [8, 8]  =  -1.28485

This seems to be a trap that will give you dense matrices in SparseMatrixCSC form. In general, Dense * Tridiagonal will be as dense as it started, so I'm not sure this was a conscious decision.

julia> @which A*Mx
*(A::AbstractArray{T,2} where T, B::AbstractArray{T,2} where T) in LinearAlgebra at C:\Users\accou\AppData\Local\Programs\Julia\Julia-1.4.1\share\julia\stdlib\v1.4\LinearAlgebra\src\matmul.jl:152

This was on v1.4, so I'm not sure if it's on master.

[mcognetta]

I worked on these in a few older prs (I think #32521 is representative). I was told it was a conscious decision. It comes from how similar is defined for structured matrix types in sparsearrays. If this decision can be revisited I'd be quite happy to help.

[dkarrasch]

The issue is on which factor do you call similar? We do that on the second factor, such that

julia> Mx*A
8×8 Array{Float64,2}:
 -1.35375   -0.780296    0.512425   …  -1.22988    -0.38358    -1.28576
  1.27656    0.045418   -1.33725        0.503869    0.398921    0.772629
 -1.67424    0.707068    0.813598      -0.389555    0.376913   -0.382437
  0.948811  -0.33374    -0.0497121     -0.0619177  -1.10717    -0.612653
  0.887939  -0.593686    0.176546       0.591326    0.928073    0.768298
 -1.10373    0.670526   -0.522282   …  -0.768006   -0.605545    0.569729
  0.150751  -0.549392    0.0865425      0.468729   -0.0574477  -1.21706
 -0.552833   0.0517309  -0.0678415     -0.239598   -0.411052    0.261905

gives dense output. If one could squeeze in better distinguishing multiplication methods without opening ambiguity hell, that would be great, but currently that's how it works.

[dkarrasch]

Closing as a dup of #27176, may be fixed by #32521.