symbol_fax.c

Part of a parallel direct block solver.  This is the generic block symbolic factorization routine.

Authors

  • Francois Pellegrini
  • Jean Roman (v0.0)

Dates

Version 0.0from 22 jul 1998 to 29 sep 1998
Version 0.1from 04 apr 1999 to 21 apr 1999
Version 0.2from 08 may 2000 to 09 may 2000
Version 1.0from 13 mar 2002 to 08 jun 2002
Version 1.2from 23 aug 2002 to 23 aug 2002
Version 2.0from 21 mar 2003 to 21 mar 2003
Summary
symbol_fax.cPart of a parallel direct block solver.
Macros
SYMBOL_FAX_ITERATORLoop for all adjacent edges, used in symbolFaxi.
SYMBOL_FAX_VERTEX_DEGREEComputes the number of adjacent edges to a vertex.
symbolFaxSymbolic factorization routine.

Macros

SYMBOL_FAX_ITERATOR

Loop for all adjacent edges, used in symbolFaxi.  Must be defined in including file if SYMBOL_FAXI_INCLUDED is defined.

Parameters

ngbdptrNeighbour pointer.
vertnumVertex index.
vertendIterator.

SYMBOL_FAX_VERTEX_DEGREE

Computes the number of adjacent edges to a vertex.

Parameters

ngbdptrNeighbour pointer.
vertnumVertex index.

symbolFax

Symbolic factorization routine.

This routine computes the block symbolic factorization of the given matrix according to the given vertex ordering.

Algorithm

The algorithm is implemented in a cache-friendly manner, by using a single dynamic array which grows along with the number of computed blocks.  The array is decomposed in the following manner:

  • In a first phase, a hash table and a sort area are reserved at the end of the space of already computed blocks.  The sort area is created far enough from the end of the array of already computed blocks such that if there are no contributing blocks all new blocks can be created without colliding with the sort area.
  • Then, in a second phase, if the current column block does have contributing column blocks, an area for simply-linked temporary blocks is reserved at least after the sort area, leaving enough space to create all of the corresponding potential new blocks just after all the blocks of the previous column block (right picture).
|ccccccccccc| <- bloktab (bloktax)
|ccccccccccc|
|ccccccccccc|                                :ccccccccccc:
|ccccccccccc| >- Computed blocks ----------< |ccccccccccc|
|ccccccccccc|                                |ccccccccccc|
|-----------|                                |:::::::::::|
|hhhhhhhhhhh| <- hashtab = bloknum --------> |bcbcbcbcbcb|
|hhhhhhhhhhh|                 |              |cbcbcbcbcbc|
|hhhhhhhhhhh|                 |              |bcbcbcbcbcb|
|hhhhhhhhhhh|                 |              |cbcbcbcbcbc|
|-----------|                 |              |bcbcbcbcbcb|
|           |                 |              |-----------|
|-----------| <- sorttab...... ------------> |           |
|sssssssssss|                                |           |
|sssssssssss|                                |           |
|-----------| <- ............................|           |
|           |                     tloktab -> |-----------|
|           |                                |ttttttttttt|
|           |                                |ttttttttttt|
:           :                                |-----------|
:___________:                                :___________:
              <- bloktab + blokmax

Parameters

symbptrSymbolic block matrix [based]
vertnbrNumber of vertices
edgenbrNumber of edges
basevalBase value
ngbdptrNeighbor bookkeeping area
ngbfrstFirst neighbor function
ngbnextNext neighbor function
ngbdegrVertex degree function (upper bound)
ordeptrMatrix ordering

Returns

0on success.
!0on error.
Incomplete symbolic factorization routine with limitation of level-of-fill value.
Close