Fortran - Nested Factorization

Author

Nested Factorization

John Appleyard

2004-05-20, 6:31 am

I've been asked about the NF benchmark in the Polyhedron 2004
Benchmarks. NF is an implementation of the "nested factorization"
iterative solver for the huge sets (millions) of linear equations which
can arise when dealing with 2D & 3D grids (e.g in finite difference
codes). The method is very effective, but not well known outside the
oil industry. There's more information, including more Fortran 90 code,
and some comparisons with other methods at www.polyhedron.com (look for
link at middle left of screen).
--
John Appleyard - (send email to john!news@.. rather than spamtrap@..)
Polyhedron Software
Programs for Programmers - QA, Compilers, Graphics, Consultancy
********* Visit our Web site on http://www.polyhedron.co.uk/ *********

Victor Eijkhout

2004-05-20, 12:33 pm

John Appleyard <spamtrap@polyhedron.com> wrote:

> I've been asked about the NF benchmark in the Polyhedron 2004
> Benchmarks. NF is an implementation of the "nested factorization"
> iterative solver for the huge sets (millions) of linear equations which
> can arise when dealing with 2D & 3D grids (e.g in finite difference
> codes). The method is very effective, but not well known outside the
> oil industry.

Hey, I've been citing your paper (with Cheshire & Pollard) frequently
when I write about ILU.

I've always wondered, your method is based on preserving column sums
(which is equivalent to mass preservation), while other people have
based "modified ILU" on preserving row sums. Is there a mathematical
justification for your approach? Have you tested the difference between
the one and the other on realistic problems?

V.

--
email: lastname at cs utk edu
homepage: cs utk edu tilde lastname

John Appleyard

2004-05-20, 2:32 pm

Victor Eijkhout wrote:

> John Appleyard <spamtrap@polyhedron.com> wrote:
>
>
>
>
> Hey, I've been citing your paper (with Cheshire & Pollard) frequently
> when I write about ILU.
>
> I've always wondered, your method is based on preserving column sums
> (which is equivalent to mass preservation), while other people have
> based "modified ILU" on preserving row sums. Is there a mathematical
> justification for your approach? Have you tested the difference between
> the one and the other on realistic problems?
>

Yes - we did a lot of tests on 3 phase black oil problems - which have 3
variables per grid block (pressure and 2 saturations), and it was pretty
clear. The recent Schlumberger white paper cited in my note says the
same. The crunch was that colsum gives material conservation while
rowsum does not; oil companies don't like to see their assets disappear!

--
John Appleyard - (send email to john!news@.. rather than spamtrap@..)
Polyhedron Software
Programs for Programmers - QA, Compilers, Graphics, Consultancy
********* Visit our Web site on http://www.polyhedron.co.uk/ *********

Victor Eijkhout

2004-05-20, 8:31 pm

John Appleyard <spamtrap@polyhedron.com> wrote:

> The crunch was that colsum gives material conservation while
> rowsum does not; oil companies don't like to see their assets disappear!

I can imagine.

I was actually thinking more about convergence period. The choice
between two preconditioners is often not a matter of which one is the
fastest, but which one will work at all. I was wondering if the nested
factorisation is any more reliable than ILU / mILU, which after all
mostly work on M-matrices and come with no guarantee outside that class.

V.
--
email: lastname at cs utk edu
homepage: cs utk edu tilde lastname

John Appleyard

2004-05-21, 2:36 pm

Victor Eijkhout wrote:
> John Appleyard <spamtrap@polyhedron.com> wrote:
>
>
>
>
> I can imagine.
>
> I was actually thinking more about convergence period. The choice
> between two preconditioners is often not a matter of which one is the
> fastest, but which one will work at all. I was wondering if the nested
> factorisation is any more reliable than ILU / mILU, which after all
> mostly work on M-matrices and come with no guarantee outside that class.
>

We did compare colsum with rowsum (and variants such as volume weighted
rowsum which were designed to get closer to material conservation) and
found colsum to be significantly better. I can't be sure now whether
the difference was just in convergence rates, or whether the rowsum
method failed to converge more often - I think both. Really, I think
the question is the wrong way round - why would one choose an arbitrary
constraint such as rowsum (or some variation that takes your fancy) when
colsum is uniquely defined and physically meaningful (and works better)?

In cases anyone's wondering, the colsum and rowsum constraints are
equivalent on symmetric matrices!

Incidentally, with a little algebraic manipulation, you can show that
nested factorization is equivalent to a strict ILU factorization with
half of the fill in bands present. That could explain, for someone with
a standard ILU perspective, why it works.

I suggest we remove comp.lang.fortran from here on (assuming you're
posting via sci.math.num-analysis).
--
John Appleyard - (send email to john!news@.. rather than spamtrap@..)
Polyhedron Software
Programs for Programmers - QA, Compilers, Graphics, Consultancy
********* Visit our Web site on http://www.polyhedron.co.uk/ *********

Sponsored Links