🚀 go-pugleaf

hcobb@fly2.berkeley.edu (Henry J. Cobb) writes:

>I am interested in C code for the manipulation of a VERY large matrix.
>Basically, what I need to do is perform an LU decomposition on a matrix
>too large to operate on the whole thing at once.  Therefore, I need an
>algorithm that allows me to operate on chunks of the matrix at a time,
>and which allows an in-place LU decomposition, so that I can minimize
>the amount of disk storage necessary for the computations.  Any
>help is GREATLY appreciated.

Assuming your matrix results from a finite analysis technique, you
should look into an out-of-core skyline matrix solver.  The only
caveat is that i/o time can be of the same order as solve time.  I have a
reference to a published Fortran code, which could be messily ported to 
C via f2c (PD fortran to C converter) or by hand (with lotsa goto's).

    AUTHOR = "G. Dhatt and G. Touzot",
    TITLE = "The finite element method displayed",
    ADDRESS = "Chichester",
    PUBLISHER = "John Wiley \& Sons",
    YEAR = "1984"}

If you go with a skyline solver, you should also consider Sloan's
algorithm, which reorders nodes to minimize the skyline.

    AUTHOR = "S. W. Sloan",
    TITLE = "A fortran program for profile and wavefront reduction",
    JOURNAL = "Int J Num Meth Eng",
    YEAR = "1989",
    VOLUME = "28",
    PAGES = "2651--2679"}

I believe the code provided is in Fortran, but you should be able to 
C it clearly (or, again, use f2c).

If you hear about any C-codes for the above, please let me know.  I'm
not thrilled about being Fortran-dependent for such things.
--
Dave!

You should also look at the optsol articles in the INternational Journal of
Numerical  Methods in Engineering (aspprox 1984), and Irons article on wave front
solvers IJNME about 1983.
-- 

Regards.
 
Don Rolph  a722756@pan.mc.ti.com WD3 MS10-13 (508)-699-1263

	I'd first like to thank everybody for their input on this, there
didn't seem to be much of a consensus on this, so we're goning to handle it
like this:

	First a quick note: we're using a RS/6000 and we expect the matrix
to be around 500+ MB.

	Our game plan is to mmap a file, map the matrix to that address
space and fork off processes to handle chunks of it using MP style code.

	Our hope is that while some of the processes are blocked, waiting
for the parts of the matrix that they've touched to be paged in, other
processes will be able to continue crunching on pages that are curently in
core.

	We can (and will) take over the machine to run this, but are
wondering what the ratio should be between:

	Demand: The combined working set of the running processes. ( = Size
of each block * number of blocks active at a time for a process * total
number of processes)

	and Supply: Total system physical memory. (64 MB minus some amount
for the OS and per process overhead).

	It seems as though Demand should be about equal to Supply, but we'd
like to hear of any studies on this.

	It might prove to be useful to overcommit a little (for some sort of
read-ahead?) or undercommit by some factor (to provide "extra caching").
At the moment we're tempted to just provide args for block-size and number
of processes and test it out that way.
--
	Henry J. Cobb	hcobb@fly2.berkeley.edu	SFB Tyrant
	"A const pointer is a steady reference,
	while a pointer to const is a pledge not to tinker."