Dense versus sparse is not a precise science. For example, it is well-known that a single dense column creates problems for interior point algorithms. Many interior point algorithms nowadays typically try to identify dense columns and split them apart or (less typically) algebraically separate them. That is because interior point methods need to solve system of equations like AA'w = y, where A is the m x n "A" matrix in the LP, A' is its transpose, y is m-vector of knowns, and w is an m-vector of unknowns. And a single dense column in A makes AA' dense.
Interior point algorithms think of a problem as sparse if the Cholesky factorization of AA' = LL' (L is a lower triangular matrix) is sparse (that is, L is sparse), possibly after dense columns are split. But that's not even the entire story because the ordering rows of A affect the sparsity of L. There is no scientific rule about when interior point algorithms work better than extreme-point algorithms. Certain problems always work better with one algorithm compared to the other, but its hard to generalize this. Interestingly, over the years some problems that at first seemed to only be solvable by interior-point algorithms are now solvable (and faster) by extreme-value algorithms. Competition between these two algorithms have helped the entire optimization field. -Marc -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Dragos Ilie Sent: Saturday, August 02, 2008 12:00 PM To: [email protected] Subject: [Help-glpk] Sparse vs. Dense problems Hi! According to the GLPK manual the interior-point solver is fit for solving sparse LP problem and is quite inefficient for dense problems. My understanding is that a sparse problem is one where most of the entries in the coefficient matrix are zero. Conversely, a dense problem has mostly non-zero entries in the coefficient matrix. Is this correct? Is there a more accurate definition or rule quantifying what "most" entries means in terms of the size of the matrix? Regards, Dragos _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk ---------------------------------------------------------------------------- This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. ---------------------------------------------------------------------------- _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
