Sparse Matrix Storage
Sparse matrix storage methods take advantage of sparsity
in large LP models, where subsets of the constraints typically
depend on only a small subset of the variables. For example, an LP
coefficient matrix for a problem with 10,000 variables and 10,000
constraints would take about 800 megabytes for matrix storage using
dense storage methods, but if this problem has the sparsity typical
of larger models, it would take about 24 megabytes using the sparse
storage methods in the LP/Quadratic Solver. (To learn more,
click on Problem Size and Sparsity,
covered in our Solver Tutorial.)
Matrix Factorization
Large LP models require hundreds of thousands to
millions of floating-point arithmetic calculations to solve. Because
of the finite precision inherent in computer arithmetic, small
numerical errors occur in these calculations. Using conventional
matrix representation and Simplex method iterations, these errors
typically have a cumulative effect, leading to a numerically
unstable problem and possibly large errors in the
"solution."
The LP/Quadratic Solver uses a factorization
of the LP matrix, called the LU decomposition, which remains
numerically stable. This factorization is updated using advanced
numerical methods (various matrix updates and dynamic
Markowitz refactorization) that are much faster than a full
update on each Simplex iteration. These methods enable the LP/Quadratic
Solver to maintain accuracy, find the optimal
solution, and do so much faster than conventional methods.
Back to Premium Solver
Platform Product Overview
