Slow triangular solves

[timweiland]

Description

Unless I messed up somewhere, tridiagonal solves are super slow.
In the example below, \ takes 200 microseconds while LinearSolve.jl takes a very long time (at least a minute, haven't waited for longer than that). I'm guessing LinearSolve.jl is trying to do a dense Cholesky, but I haven't looked into it. Same problem occurs for Tridiagonal.

MWE

using LinearSolve, LinearAlgebra

ρ, k = 0.95, 10000
A_tri = SymTridiagonal(ones(k) .+ ρ^2, -ρ * ones(k-1))
z = rand(k)

prob = LinearProblem(A_tri, z)

@time A_tri \ z # 200 microseconds on my machine
@time solve(prob) # > 1 minute, probably more than that

Expected behaviour

The use of some algorithm specialised for tridiagonal matrices, e.g. Thomas algorithm, and thus runtimes on par with \

Version

LinearSolve v3.24.0

[ChrisRackauckas]

Closed by #672