¡@¡@The success of IPM heavily depends on linear algebra schemes therein. In this talk, we first examine four topics with particular relevance to LP. (1) We explore the special structures of the linear systems arising in IPM. (2) We devise efficient algorithms for finding the search directions in interior point linear programming. Solving these linear systems consume most of the computational efforts in IPM. (3) We propose an algorithm to handle ill-conditioned linear systems in the endgame of IPM. We also prove the convergence of the algorithm. (4) We demonstrate the numerical results. The results show that our algorithms are superior to other state-of-the-art packages especially in large scale problems.

¡@¡@On the other hand, linear programming problems with massive variables and moderate number of constraints are considered. Column generation principles and cutting plane methods (row generation) are popular schemes to manage the large number of variables and constrains, respectively. We propose an interior point type of algorithm that combines the idea of column generation and row generation. Numerical results for the airline crew scheduling problems that up to 800 constraints and more than 6,600,000 variables reveal significant improvement over the traditional algorithms.

¡@¡@Finally, many theoretical and algorithmic results of IPM in LP can be extended to SDP in parallel. We briefly introduce the setups and challenges of using IPM for SDP in the viewpoint of computational linear algebra.