Chemical process simulation matrices from Nils van Velzen, VORtech Computing. Added March, 2006. These require a Dulmage-Mendelsohn decomposition (see cs_dmperm in CSparse). Since UMFPACK v4.6 does not include a dmperm preordering, the fillin can be higher than it should be. -------------------------------------------------------------------------------- Email from Nils van Velzen: -------------------------------------------------------------------------------- I'm using UMFPACK for some time as part of a nonlinear solver, that is used to solve large systems of nonlinear equations (production of ethylene). Before we used UMFPACK, we first applied a lower block decomposition where after we permuted the diagonal blocks in order to minimise the bandwidth and used an lu-decomposition that only permuted for numerical stability. When the model became more complex it became harder to keep the bandtwidht small and UMFPACK decreased the computational speed up to a factor 40. I have however a number of cases where UMFPACK performs significally worst than a LU-decomposition without a reordering strategy (except for numerical stability). The difference is over a factor 4 and I have a case I cannot solve using UMFPACK due to an allocation error. I do not think that this is a "bug", and I've found a good strategy for selecting between UMFPACK and my old decomposition algorithm, but I wonder whether you are interested in these test cases. If you are interested, please let my know, the matrices are approx 6 MB each. Kind regards, Nils van Velzen Numerical Software Engineer, VORtech Computing, The Netherlands nils at vortech dot (country code for The Netherlands) -------------------------------------------------------------------------------- My intention is to use it only for the diagonal blocks. I know I take a risk, where I create in theory a numerical singular matrix, but this has never happened. There are still a number of things I have to figure out before I can use UMFPACK on all the diagonal elements. The structure of our system is that we have one very large diagonal block and all large number of relative small blocks. In my current implementation I only use UMFPACK for the largest diagonal block, and my "old" solver for the other blocks. And this works very fine for the time being. There are two issues I have to investigate first before applying UMFPACK for all diagonal blocks (at ones), and maybe you know the answers by hart. 1) Does the AMD/UMFPACK reordering preserve the diagonal blocks, that means does it only permute within the blocks. because I'd like to apply it to the diagonal blocks using a single call (decomposing the blocks one at a time will destroy the performance, I've already tried this a few years ago when I experimented combining different solvers) 2) I have to figure out the data structures (LU-decomposition) of UMFPACK because I have to program my back-substitution for my lower block matrix and LU-decomposition of the diagonal blocks. I'll collect a number of my linear systems (that cause problems) and will upload them to you including a readme-file explaining the format. Kind regards, Nils van Velzen. -------------------------------------------------------------------------------- Hi, A number of test matrices that are hard (in the sense of computational time) to solve by UMFPACK + additional information. Uploading them all at onces did not work. Therefore I'll try to send it in small bits. The first part contains the most relevant information. (matrices only containing the diagonal blocks) The other parts will contain the "full" matrices before block decomposition. (see info in tar.gz-file) -------------------------------------------------------------------------------- part 2: the complete Jacobians of Zd. -------------------------------------------------------------------------------- part 3: the complete Jacobians of std1. -------------------------------------------------------------------------------- Description of the matrices, and results: -------------------------------------------------------------------------------- Matrices that are "hard" to solve using UMFPACK. The directories contains (Jacobian) matrices of two models: *std1 *Zd The number in the filename corresponds to the iteration number of the non-linear solver. Jac contains the whole Jacobian matrix Jac_db only contains the diagonal blocks (lower block triangularisation) For both models, UMFPACK performs relativly good for the second iteration. As a result of the initial guess. The sparsity pattern changes slightly during the first few iterations. At the third iteration however UMFPACK is significally slower than an LU-decomposition without ordering. As an indication I present a number of test results (note UMFPACK is approx a factor 1.5 faster when using blas of K. Goto, but these results using imsl-BLAS were the most easy to produce and the exact timings are not relevent): Times in seconds, computing lu-decomposition of diagonal blocks (symbolic+numeric step for UMFPACK), using Win XP, Pentium IV, 3.4 GHz, 1Gb Ram. normal LU UMFPACK model iteration cpu wall cpu wall std1 2, 2.219, 2.219, 2.500, 2.516 std1 3, 2.266, 2.266, 34.547, 34.594 Zd2 2, 3.859, 3.860, 3.594, 3.593 Zd2 3, 3.969, 3.985, 32.766, 32.828 Zd2 6, 3.359, 3.359, 29.797, 29.797 Nils van Velzen VORtech Computing The Netherlands Marco van Goethem Technip Benulux b.v. The Netherlands mvangoethem at technip dot com