# Most efficient way of computing B'\* inv(A)\* B for A large

**URL:** <https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513>\
**Category:** Specific Domains\
**Tags:** linearalgebra\
**Created:** [September 29, 2020, 9:31pm UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513 "2020-09-29T21:31:28Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [September 30, 2020, 12:02am UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/21 "2020-09-30T00:02:44Z")

</div>

Is this model reduction?

---

<div class="post-metadata">

**Author:** ![Joris\_Pinkse](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joris_pinkse/32/216398_2.png) [@Joris\_Pinkse](https://discourse.julialang.org/u/Joris_Pinkse)\
**Post date:** [September 30, 2020, 12:04am UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/22 "2020-09-30T00:04:14Z")

</div>

For the sake of completeness, B’\*inv(A)\*B does better than I’d thought: 0.45 seconds on second run.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [September 30, 2020, 12:08am UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/23 "2020-09-30T00:08:12Z")

</div>

Can tullio incorporate symmetry?

---

<div class="post-metadata">

**Author:** ![Joris\_Pinkse](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joris_pinkse/32/216398_2.png) [@Joris\_Pinkse](https://discourse.julialang.org/u/Joris_Pinkse)\
**Post date:** [September 30, 2020, 12:10am UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/24 "2020-09-30T00:10:12Z")

</div>

@PetrKryslUCSD I’m using it for some optimization problem in many variables. I can simplify this by writing it as a nested problem with the inner nest a bunch of high-dimensional problems. The Hessian of the outer problem then becomes the sum over terms of the form C-B’A^{-1}B, where the A’s are the Hessians of the inner problem.

---

<div class="post-metadata">

**Author:** ![Joris\_Pinkse](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joris_pinkse/32/216398_2.png) [@Joris\_Pinkse](https://discourse.julialang.org/u/Joris_Pinkse)\
**Post date:** [September 30, 2020, 12:11am UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/25 "2020-09-30T00:11:30Z")

</div>

Good question; I don’t know. Doesn’t look like it.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [September 30, 2020, 2:14am UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/26 "2020-09-30T02:14:22Z")

</div>

It looks like you may be trying to solve a system with

\begin{bmatrix} A & B \\ B^T & -C \end{bmatrix}.

If C is also positive definite, you can factorize the above matrix directly while taking advantage of its structure using [https://github.com/JuliaSmoothOptimizers/LDLFactorizations.jl](https://github.com/JuliaSmoothOptimizers/LDLFactorizations.jl).

---

<div class="post-metadata">

**Author:** ![Joris\_Pinkse](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joris_pinkse/32/216398_2.png) [@Joris\_Pinkse](https://discourse.julialang.org/u/Joris_Pinkse)\
**Post date:** [September 30, 2020, 2:14pm UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/27 "2020-09-30T14:14:56Z")

</div>

Not quite. But yes, partitioned inverses are related.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [September 30, 2020, 2:48pm UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/28 "2020-09-30T14:48:06Z")

</div>

> [@Joris\_Pinkse](#):
>
> `D[:,:] = A \ B`

If you’re looking for the inplace version of backsolve it’s `ldiv!()`.  
More generally, the syntax to write into a matrix `D` is `D .= ...`.

---

<div class="post-metadata">

**Author:** ![Joris\_Pinkse](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joris_pinkse/32/216398_2.png) [@Joris\_Pinkse](https://discourse.julialang.org/u/Joris_Pinkse)\
**Post date:** [September 30, 2020, 2:49pm UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/29 "2020-09-30T14:49:01Z")

</div>

Ha, I knew about ldiv, but thought .= was only for assigning scalars, thanks!

---

<div class="post-metadata">

**Author:** ![Joris\_Pinkse](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joris_pinkse/32/216398_2.png) [@Joris\_Pinkse](https://discourse.julialang.org/u/Joris_Pinkse)\
**Post date:** [September 30, 2020, 3:42pm UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/30 "2020-09-30T15:42:42Z")

</div>

Tried another run between some major contenders with B 3\_000 by 10. The difference between the first four contenders is small. I’m surprised at the gain of using MKL (my computer has an AMD processor).

function one()  
D.= cholesky(A).U \ B  
@tullio C[i,j] = D[k,i] \* D[k,j]  
end

function two()  
ldiv!(D, cholesky(A).U, B)  
@tullio C[i,j] = D[k,i] \* D[k,j]  
end

function three()  
D .= cholesky(A).U \ B  
C .= D’ \* D  
end

function four()  
ldiv!(D, cholesky(A).U, B)  
C .= D’ \* D  
end

function five()  
C.= B’ \* inv(cholesky(A)) \* B  
end

with openblas:

61.508 ms (40 allocations: 68.89 MiB)  
61.744 ms (36 allocations: 68.67 MiB)  
61.966 ms (15 allocations: 68.89 MiB)  
61.603 ms (11 allocations: 68.67 MiB)  
142.128 ms (15 allocations: 137.56 MiB)

with mkl:

34.641 ms (40 allocations: 68.89 MiB)  
34.490 ms (36 allocations: 68.67 MiB)  
34.084 ms (15 allocations: 68.89 MiB)  
33.951 ms (11 allocations: 68.67 MiB)  
129.186 ms (15 allocations: 137.56 MiB)

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [September 30, 2020, 4:19pm UTC](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513/31 "2020-09-30T16:19:04Z")

</div>

What if you do the loops by hand with LoopVectorization, taking into account the symmetry. Can you halve the fastest time?

[Previous page](https://discourse.julialang.org/t/most-efficient-way-of-computing-b-inv-a-b-for-a-large/47513.md?page=1)
