2
$\begingroup$

I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few constraints (say, 50 constraints and 5000 variables or more), so I thought that was ok.

Then I decided to implement a basis refactorization approach, so I chose the Forrest-Tomlin basis update approach. I observed that the program became much slower! I would like to understand why and whether this is expected for the kinds of problems (few constraints, many variables) that I consider.

A few words on how I have implemented Forrest-Tomlin. Say that the initial basis matrix is factorized as $B = LU$. After $k$ updates, I have a factorization $B = LR_1\cdots R_k U$ (I am for simplicity ignoring the permutation matrices involved). Then to solve the system $Bx = b$ I have to solve $L R_1 \cdots R_k y = b$ and then $Ux = y$. Solving $L R_1 \cdots R_k y = b$ is easy since the matrices $R_i$ are very special; solving a system $R_i x = b$ takes linear time.

What I have observed after profiling is that most of the time was spent solving systems with the $R_i$ matrices. With Forrest-Tomlin there is an added cost to solve a system, and since I have many more columns than rows, to find the incoming variable I have to solve many systems, which becomes less efficient the more updates I make. And this extra cost is much higher than computing the LU decomposition from scratch.

Does this make sense? Am I missing something?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.