# Sparse solve vs BandedMatrix; time and allocation surprise
**URL:** https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119
**Category:** Performance
**Created:** [August 17, 2020, 4:48pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119 "2020-08-17T16:48:24Z")
**Posts on this page:** 10
**Page:** 2
### Author:  [@ctkelley](https://discourse.julialang.org/u/ctkelley)
#### Post date: [August 27, 2020, 8:35pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/21 "2020-08-27T20:35:32Z")
Is this a reasonable way to open the issue?
–
@ChrisRackauckas suggests that I raise this issue. It came up on
`[Sparse solve vs BandedMatrix; time and allocation surprise](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119)
Is it reasonable for spdiagm to return a banded matrix and use the LAPACK
band solvers if the bandwidth is sufficiently narrow?
Right now you get a general sparse matrix and SuiteSparse does the solve.
> > Show the example from discourse
Matlab seems to do the right thing
> > Show them the other example
---
### Author:  [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)
#### Post date: [August 27, 2020, 9:50pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/22 "2020-08-27T21:50:38Z")
> [@ctkelley](#):
>
> Is it reasonable for spdiagm to return a banded matrix and use the LAPACK
> band solvers if the bandwidth is sufficiently narrow?
[Type parameter for whether bidiagonal matrix is low(:L) bidiagonal or up(:U) bidiagonal. · Issue #33402 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/33402) is another case where banded matrices could/should be used in Base as the output type of an operation to allow for further optimizations, but currently the output is just a pure sparse matrix. @dlfivefifty mentioned in [Check bands for zeros in `lu!` and `qr!` · Issue #197 · JuliaLinearAlgebra/BandedMatrices.jl · GitHub](https://github.com/JuliaMatrices/BandedMatrices.jl/issues/197#issuecomment-680046851) that it can’t be added to the StdLib yet because of ArrayLayouts.jl, but I think there’s more than a few cases where Base should be using BandedMatrix types in some places and so the only way to get the efficient algorithm would be to have some form of a BandedMatrix in Base, or to just copy some of the methods over and have the best possible algorithm in Base.
Banded matrices just show up as such a common form that I think we’re losing out by not having them in our pool of go-to things that Base is allowed to give you and specialize on.
---
### Author:  [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)
#### Post date: [August 27, 2020, 9:52pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/23 "2020-08-27T21:52:34Z")
So yes, let’s get an issue in Base to discuss this more. @dlfivefifty would you want to lead this to discuss what would need to be done in order to make that possible?
---
### Author:  [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)
#### Post date: [August 27, 2020, 9:53pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/24 "2020-08-27T21:53:16Z")
👍
---
### Author:  [@ctkelley](https://discourse.julialang.org/u/ctkelley)
#### Post date: [August 27, 2020, 11:17pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/25 "2020-08-27T23:17:48Z")
@dlfivefifty, are you taking ownership of this issue? That would be fine with me and you have more gravitas on this topic than I do.
— Tim
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [August 28, 2020, 12:40am UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/26 "2020-08-28T00:40:48Z")
> [@ctkelley](#):
>
> Is it reasonable for spdiagm to return a banded matrix and use the LAPACK
> band solvers if the bandwidth is sufficiently narrow?
No. That would be type-unstable.
> [@ctkelley](#):
>
> Margin of victory = some surprise
A factor-of-10 slowdown between a generic sparse-direct solve, which assumes no matrix structure, and a specialized banded-matrix solve seems totally unsurprising to me. If you have a structured matrix, you should use a structured-matrix type to take advantage of it.
---
### Author:  [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)
#### Post date: [August 28, 2020, 9:53am UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/27 "2020-08-28T09:53:18Z")
[https://github.com/JuliaLang/julia/issues/37258](https://github.com/JuliaLang/julia/issues/37258)
---
### Author:  [@ctkelley](https://discourse.julialang.org/u/ctkelley)
#### Post date: [August 28, 2020, 10:15am UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/28 "2020-08-28T10:15:29Z")
Nicely done. It’ll be interesting to see where this goes.
---
### Author:  [@Rajesh\_Nakka](https://discourse.julialang.org/u/Rajesh_Nakka)
#### Post date: [May 15, 2022, 1:14pm UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/29 "2022-05-15T13:14:17Z")
In a problem, till now, I was using sparse matrices (of size ~= `(1_000_000, 1_000_000)`) for
matrix-vector `\` operation.
Now, I have realized that my matrix has a descent banded structure so I want to gain benefit from this.
[this blog](https://www.google.com/url?q=https://approximatelyfunctioning.blogspot.com/2018/12/banded-matrices-and-ordinary.html&sa=D&source=hangouts&ust=1652705907687000&usg=AOvVaw1gzZKMkH3D2EKqBWxR36fV) and the current thread of discussion, says that I would probably get a performance improvement.
In the flow of a program, I have a `SparseMatrixCSC` type matrix which needs to be converted to `BandedMatrix` type before using with `\` operator.
I wrote the following piece of code for converting `SparseMatrixCSC` to `BandedMatrix`.
```julia
function banded_matrix(A::SparseMatrixCSC)
I, J, V = findnz(A)
vals = Dict{Int, Vector{Float64}}()
for (ai, aj, av) in zip(I, J, V)
d_ij = ai-aj
if d_ij in keys(vals)
push!(vals[d_ij], av)
else
vals[d_ij] = [av,]
end
end
A = BandedMatrix(
Tuple((k => v for (k, v) in vals)),
size(A),
)
return A
end
```
Running this is giving `StackOverflowError`.
@dlfivefifty, Please let me know if there is any method already available in [BandedMatrices.jl](https://github.com/JuliaMatrices/BandedMatrices.jl) for this sparse to banded matrix conversion.
Thanks,
---
### Author:  [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)
#### Post date: [May 16, 2022, 9:47am UTC](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119/30 "2022-05-16T09:47:22Z")
No there’s not yet a method. Probably the best approach would be to implement `bandwidths(::SparseMatrixCSC)`, create a zero banded matrix with those bandwidths, then just iterate through the nonzero entries calling `banded_setindex!`
[Previous page](https://discourse.julialang.org/t/sparse-solve-vs-bandedmatrix-time-and-allocation-surprise/45119.md?page=1)