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