# Add a UpperHessenberg row in LinearAlgebra.factorize?

**URL:** <https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530>\
**Category:** General Usage\
**Tags:** linearalgebra\
**Created:** [April 29, 2025, 3:35pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530 "2025-04-29T15:35:45Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [April 29, 2025, 3:35pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/1 "2025-04-29T15:35:45Z")

</div>

My intuition is that there should also be a row about `UpperHessenberg` in this table (and what should be a proper factorization for it). Does my idea make sense?

 ![image](https://global.discourse-cdn.com/julialang/original/3X/8/b/8b88182178bf8630131b240aa32c4ba3ea62ca1e.png)

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [April 29, 2025, 5:26pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/2 "2025-04-29T17:26:57Z")

</div>

Although `UpperHessenberg` is a factorization, in a sense, it is never returned by `factorize` (even when the input is `UpperHessenberg`) so it should not be in this table as an output structure. As for input structure, something with `UpperHessenberg` structure follows the already-listed rules:

```julia-repl
julia> factorize(UpperHessenberg(randn(3, 3))) # LU in general
LU{Float64, Matrix{Float64}, Vector{Int64}}
L factor:
3×3 Matrix{Float64}:
  1.0 0.0 0.0
 -0.884411 1.0 0.0
 -0.0 0.419893 1.0
U factor:
3×3 Matrix{Float64}:
 -1.07354 -0.0216093 -1.83604
  0.0 -2.24899 -1.79199
  0.0 0.0 1.88132

julia> factorize(UpperHessenberg(triu!(randn(3, 3)))) # UpperTriangular if so
3×3 UpperTriangular{Float64, UpperHessenberg{Float64, Matrix{Float64}}}:
 0.472389 0.63327 1.01618
  ⋅ -1.58879 -0.534824
  ⋅ ⋅ -0.119193

julia> factorize(UpperHessenberg(diagm(randn(3)))) # Diagonal if so
3×3 Diagonal{Float64, Vector{Float64}}:
 0.0997544 ⋅ ⋅
  ⋅ -2.56062 ⋅
  ⋅ ⋅ -0.573808

```

One could collect a (partial) list of “fast-solving” types somewhere else, but `factorize` is not the place.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 29, 2025, 5:43pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/3 "2025-04-29T17:43:53Z")

</div>

> [@WalterMadelim](#):
>
> My intuition is that there should also be a row about `UpperHessenberg` in this table (and what should be a proper factorization for it). Does my idea make sense?

You usually don’t need to factorize an upper-Hessenberg matrix: if H is upper-Hessenberg, you can already solve Hx =b in linear time in the number of nonzeros (i.e. O(n^2) for n \times n upper-Hessenberg). This is already implemented in Julia: [(H+­μI) \ x solvers for Hessenberg factorizations by stevengj · Pull Request #31853 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/31853)

In particular, not only can you do `x = H \ b`, but it also implements an in-place algorithm accessible via `ldiv!(H, x .= b)`, including an in-place algorithm for shifted systems (H + \mu I)x = b without modifying H.

If you have an _arbitrary_ matrix A, then there is an upper-Hessenberg factorization A = Q H Q^\* that is already implemented in Julia. This is used internally as a first step for eigensolves, but is useful in its own right if you need to solve systems with A + \mu I = Q (H + \mu I) Q^\* for many different shifts \mu, since you can re-use the same Hessenberg factorization H for all the shifts.

That being said, there is an open issue to support more functionality for Hessenberg matrices, and in particular fast QR, Schur, and eigen factorizations: [more methods for Hessenberg factorizations · Issue #625 · JuliaLang/LinearAlgebra.jl · GitHub](https://github.com/JuliaLang/LinearAlgebra.jl/issues/625)

---

<div class="post-metadata">

**Author:** ![danielwe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielwe/32/35657_2.png) [@danielwe](https://discourse.julialang.org/u/danielwe)\
**Post date:** [April 29, 2025, 5:50pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/4 "2025-04-29T17:50:34Z")

</div>

There is a specialized, fast `ldiv!(::UpperHessenberg, _)` method, but the dispatch isn’t set up such that you hit a fast path for `\(::UpperHessenberg, _)`. The latter falls back to the generic `\`, which sends you through an LU factorization.

```julia-repl
julia> @which UpperHessenberg([1.0 2.0; 3.0 4.0]) \ [5.0; 6.0]
\(A::AbstractMatrix, B::AbstractVecOrMat)
     @ LinearAlgebra ~/.julia/juliaup/julia-1.11.5+0.aarch64.apple.darwin14/share/julia/stdlib/v1.11/LinearAlgebra/src/generic.jl:1118

```

=\> [LinearAlgebra.jl/src/generic.jl at release-1.11 · JuliaLang/LinearAlgebra.jl · GitHub](https://github.com/JuliaLang/LinearAlgebra.jl/blob/release-1.11/src/generic.jl#L1118-L1135)

Seems like the implementation is focused on making `Hessenberg` factorization objects performant, rather than raw `UpperHessenberg` instances.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 29, 2025, 5:52pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/5 "2025-04-29T17:52:27Z")

</div>

> [@mikmoore](#):
>
> `factorize(UpperHessenberg(randn(3, 3))) # LU in genera`

Calling `factorize` on `UpperHessenberg` is currently a bad idea, because it ends up just calling an O(n^3) algorithm that doesn’t exploit the structure. The key point, however, is that factorization is not needed: you can use the matrix as-is in a solve.

> [@danielwe](#):
>
> There is a specialized, fast `ldiv!(::UpperHessenberg, _)` method, but the dispatch isn’t set up such that you hit a fast path for `\(::UpperHessenberg, _)`. The latter falls back to the generic `\`, which sends you through an LU factorization.

Yikes, that’s an oversight, probably I thought `\` dispatched to `ldiv!` at the time (the way it does for `Factorization` objects)? Should be an easy fix to add a specialized dispatch for this: [add missing methods for division of Hessenberg matrices by stevengj · Pull Request #1322 · JuliaLang/LinearAlgebra.jl · GitHub](https://github.com/JuliaLang/LinearAlgebra.jl/pull/1322)

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [April 30, 2025, 4:08am UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/6 "2025-04-30T04:08:25Z")

</div>

> [@stevengj](#):
>
> Calling `factorize` on `UpperHessenberg` is currently a bad idea

Does this also mean that calling `factorize` on a `Tridiagonal` is also undesired?  
Note that `Tridiagonal` is simpler than `UpperHessenberg`.

```julia
julia> A
4×4 Tridiagonal{Int64, Vector{Int64}}:
 1 2 ⋅ ⋅
 1 2 3 ⋅
 ⋅ 2 3 4
 ⋅ ⋅ 3 4

julia> @which factorize(A)
factorize(A::Tridiagonal)
     @ LinearAlgebra K:\julia-1.11.4\share\julia\stdlib\v1.11\LinearAlgebra\src\lu.jl:656

julia> # in the place above, I see `factorize(A::Tridiagonal) = lu(A)`

julia> @which lu(A)
lu(A::AbstractMatrix{T}, args...; kwargs...) where T
     @ LinearAlgebra K:\julia-1.11.4\share\julia\stdlib\v1.11\LinearAlgebra\src\lu.jl:341

```

And this behavior is documented in the table (the image in my first post above).

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 30, 2025, 4:26am UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/7 "2025-04-30T04:26:41Z")

</div>

> [@WalterMadelim](#):
>
> Does this also mean that calling `factorize` on a `Tridiagonal` is also undesired?

No, because there is also a specialized factorization method for tridiagonal matrices. Although it’s true that you can solve tridiagonal systems directly, in linear time, without additional factorization.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [April 30, 2025, 6:38am UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/8 "2025-04-30T06:38:17Z")

</div>

> [@stevengj](#):
>
> In particular, not only can you do `x = H \ b`, but it also implements an in-place algorithm accessible via `ldiv!(H, x .= b)`, including an in-place algorithm for shifted systems (H + \mu I)x = b without modifying H.
> 
> If you have an _arbitrary_ matrix A, then there is an upper-Hessenberg factorization A = Q H Q^\* that is already implemented in Julia. This is used internally as a first step for eigensolves, but is useful in its own right if you need to solve systems with A + \mu I = Q (H + \mu I) Q^\* for many different shifts \mu, since you can re-use the same Hessenberg factorization H for all the shifts.

Is there a special syntax for that?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 30, 2025, 12:19pm UTC](https://discourse.julialang.org/t/add-a-upperhessenberg-row-in-linearalgebra-factorize/128530/9 "2025-04-30T12:19:32Z")

</div>

> [@RoyiAvital](#):
>
> Is there a special syntax for that?

For the shifted solve? If you have a Hessenberg factorization object `F`, you can just do `(F + μ*I) \ b`, or `ldiv!(F + μ*I, b)`, and it will compute (A + \mu I)^{-1} b without modifying the factorization. This is described in the [`hessenberg` documentation](https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#LinearAlgebra.hessenberg). If you have an `UpperHessenberg` or `SymTridiagonal` matrix `H`, you can pass a `shift=μ` keyword parameter to `ldiv!`.