Group Mulvey

Group Description
Multistage stochastic financial modelling.  J. Mulvey, Princeton.
Matrices provided by Ed Rothberg, Silicon Graphics, Inc.
From the paper:

	A. Berger, J. Mulvey, E. Rothberg, and R. Vanderbei,
	"Solving multistage stochastic programs using tree dissection,"
	tech. report SOR-97-07, Program in Statistics and Operations
	Research

Ed Rothberg, email: rothberg :at the domain: multnomah.engr.sgi.com
John Mulvey, email: mulvey :at the domain: macbeth.Princeton.edu 

A stochastic programming matrix in an interior-point algorithm
for financial portfolio optimization.

Random nonzero values added (finan512.rsa) by Tim Davis.  The values were
then modified to ensure that the matrix was symmetric positive definite.

This matrix is quite strange, and appears to be highly sensitive to
tie-breaking issues, or some other phenomenon...  See the paper, above,
for a description of the phenomenon.

The following ordering algorithms were run
on a Sparc-10.  AMDperm is the Approximate Minimum Degree method, with
various "elbow room" sizes (see TR-94-038),
based on upper bounds on the external degree.
AMDtry3 is AMD with a different tie-breaking strategy.  oldAMDt is the same
as MA27, except that exact degree computations are replaced with an upper
bound on the true degree.  initMD is MA27, and origMD is a modification in MUPS
that ignores the computation of degrees above a certain threshold.  MMD is
Joseph Liu's multiple minimum degree algorithm (with delta = 0, 1, and 2).
ND is the nested dissection algorithm in Sparspak, and QMD is the minimum
degree ordering algorithm in Sparspak.  The columns in the table are
the number of nonzeros in L, the Mflops needed to compute L, the ordering
time, the number of garbage collections, the memory usage (excluding O(n)-size
arrays), and the number of size-n work arrays.

NOTE: Lnz is the number of nonzeros in the strictly lower diagonal part.
The A+AT number is the number of off-diagonal nonzeros in A+A^T.
Since this is a symmetric matrix, that's just the nonzeros in A minus n.

Matrix Portfolio/finan512.psa.gz n  74752 Anz   596992 A+AT   522240 -
Method:delta/elbow Lnz      LL^Tmflops      time comp memory O(n)usage
AMDperm:      3361993       1035.385920      5.53    0    833747  8
AMDperm:4     3361993       1035.385920      5.47    0    833747  8
AMDperm:3     3361993       1035.385920      5.63    1    776090  8
AMDperm:2     3361993       1035.385920      5.66    1    671745  8
AMDperm:1     3361993       1035.385920      5.64    1    671745  8
AMDtry3:      2522769        536.937792      5.18    0    797305  9
oldAMDt:      9285069      14968.698880      5.90    0    996344  8
 initMD:      9285069      14968.315904     10.07    0   1000263  7
 origMD:      9237356      14654.392320      6.56    0   1036206  7
    MMD:0     6432433       5933.023232    292.65    0    522240  7
    MMD:1     6432433       5933.025280    291.97    0    522240  7
    MMD:2     6432433       5933.025280    278.82    0    522240  7
     ND:      8530875       3412.739840      6.20    0    522240  5
    QMD:      4345895       2121.354368    970.03    0    522240  9


These minimum degree algorithms do show large variations in ordering times for
other matrices, but they usually produce comparable results.  This matrix
(finan512) is a very unusual exception.  The bcsstk30 matrix shows
more typical relative results, for example:


Matrix HB/bcsstk30.psa           n  28924 Anz  2043492 A+AT  2014568 -
Method:delta/elbow Lnz      LL^Tmflops      time comp memory O(n)usage
AMDperm:      3768625        899.876992      2.30    0   2088703  8
AMDperm:4     3768625        899.876992      2.31    0   2088703  8
AMDperm:3     3768625        899.876992      2.29    0   2088703  8
AMDperm:2     3768625        899.876992      2.31    0   2088703  8
AMDperm:1     3768625        899.876992      2.76    1   2072417  8
AMDtry3:      3764679        916.359040      2.32    0   2088942  9
oldAMDt:      4518625       1363.998720      2.23    0   2107723  8
 initMD:      4583033       1409.133568      2.66    0   2107538  7
 origMD:      4487456       1336.230912      2.73    0   2135673  7
    MMD:0     3849328        938.700288      4.63    0   2014568  7
    MMD:1     3863974        955.433984      4.53    0   2014568  7
    MMD:2     3886867        963.582848      4.29    0   2014568  7
     ND:      5743266       2204.590848     12.11    0   2014568  5
    QMD:      4689554       1586.877184     59.55    0   2014568  9
Displaying all 2 collection matrices
Id Name Group Rows Cols Nonzeros Kind Date Download File
752 finan512 Mulvey 74,752 74,752 596,992 Economic Problem 1997 MATLAB Rutherford Boeing Matrix Market
753 pfinan512 Mulvey 74,752 74,752 596,992 Duplicate Economic Problem 1997 MATLAB Rutherford Boeing Matrix Market