About the Cholesky decomposition in the barrier method
AnsweredHello,
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

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ł 
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

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ł
Please sign in to leave a comment.
Comments
3 comments