Solver Advanced Tutorial - Handling Sparsity in the Jacobian DirectlyHandling Sparsity in the Jacobian DirectlyWhen we wrote the constraint functions in the Product Mix example, we included terms such as "0 times x3" in
...so that we could treat the constraints uniformly, use the SUMPRODUCT function in Excel (or equivalent FOR loops in Visual Basic or another language), and easily describe the Jacobian matrix. But we recognized that this constraint does not depend on x3, the number of Speakers produced -- it has a zero partial derivative with respect to x3. Looking at the entire Jacobian matrix for the Product Mix model, we see that it contains several zero elements.
In large optimization models, the Jacobian matrix often contains a great many zero elements. In fact, in LP models with tens of thousands of variables and constraints, it is common for only 2% to 3% of the elements to be nonzero. A matrix with many zero elements is called sparse; a matrix with mostly nonzero elements is called dense. A matrix of a few hundred, or even a thousand rows and columns doesn't take that much memory, by modern standards. But a 10,000 by 10,000 matrix of double precision numbers (8 bytes each) would require 800 megabytes of RAM -- more than the memory available on most PCs today -- if all of the zero elements were stored explicitly. A better alternative is to store only the nonzero elements and their indices. Solver engines designed for large-scale problems, such as the Large-Scale LP Solver, Large-Scale GRG Solver, Large-Scale SQP Solver, KNITRO Solver, MOSEK Solver, Gurobi Solver and XPRESS Solver, are designed to exploit sparsity in the Jacobian matrix. In the Premium Solver products for Excel, zero elements in the Jacobian are detected automatically, and only nonzero elements are passed to the Solver engines. The Solver SDK products provide a convenient way to define a sparse matrix, using the DoubleMatrix object. You can, for example, define a DoubleMatrix object MyMatrix with 10,000 rows and columns, and assign values to different elements with syntax such as MyMatrix[i,j] = value just as you would for a two-dimensional array, but MyMatrix will store only the non-zero elements of the matrix. |