About the Cholesky decomposition in the barrier method

Answered

Comments

3 comments

  • Jaromił Najman

    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
    Comment actions Permalink
  • Bo Yang

    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
    Comment actions Permalink
  • Jaromił Najman

    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
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk