About the Cholesky decomposition in the barrier method

Answered

Bo Yang

• August 18, 2021 20:28

Hello,

I'm curious why Gurobi uses Cholesky decomposition to solve the linear system in the barrier method, instead of Gaussian elimination.

In the Appendix C of the book Convex Optimization., Boyd, S., & Vandenberghe, L. (2004), the authors say that Gaussian elimination can take advantage of the matrix structure so it has much lower complexity than the Cholesky decomposition in some cases. 

So can't Gurobi be much faster (or achieve similar performance in the worst case) by using Gaussian elimination? What is the bottleneck/difficulty of doing it?

Best,

Bo

0

• Official comment

  

  Simranjit Kaur

  Gurobi Staff

  • December 06, 2024 00:27

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  Gurobi Staff

  • August 19, 2021 13:28

  Hi Bo,

  I am wondering where you found this statement. In C.3.1 of Boyd's and Vandenberghe's Book, I see

  The standard algorithm for computing an LU factorization is called Gaussian elimination with partial pivoting or Gaussian elimination with row pivoting.

  Then, the authors mention 2 specific applications for banded and sparse matrices.

  In C.3.2 the authors then discuss the Cholesky factorization which is the same as LU but specialized for symmetric and positive definite matrices, meaning that \(A = LU = LL^T\) in this case. The complexity is stated to be a factor 2 lower than the standard LU factorization.

  Please let me know if I missed something.

  Best regards,
  Jaromił

   

  0
• 

  Bo Yang

  • August 19, 2021 20:42

  

  

  

  Hi Jaromil,

  Thank you for the response.

  Actually I'm referring to C.4.1 where the authors mention that using the block elimination to the banded and diagonal matrices can significantly benefit the solving process. I'm wondering whether Gurobi has implemented these techniques.

  I mistakenly wrote Gaussian elimination instead of block elimination in the question. Sorry for the confusion.

  Best,

  Bo

  0
• 

  Jaromił Najman

  Gurobi Staff

  • August 23, 2021 10:15

  Hi Bo,

  Gurobi implements most of the standard techniques such as, e.g., block elimination mentioned in Boyd's and Vandenberghe's Book. You can use the BarOrder parameter to choose the ordering performed before the Barrier algorithm which directly affects the final block decomposition algorithms.

  Best regards,
  Jaromił

  0

Post is closed for comments.