Scotch Brand 5.1.10, User Manual

Page 1: ...sparse matrix block ordering of graphs and meshes hypergraphs It gives brief descriptions of the algorithms details the input output formats instructions for use installation procedures and provides...

Page 2: ...rid incomplete nested dissection 15 3 2 1 Minimum Degree 15 3 2 2 Nested dissection 15 3 2 3 Hybridization 16 3 2 4 Performance criteria 16 3 2 5 Ordering methods 17 3 2 6 Graph separation methods 18...

Page 3: ...rings 56 7 3 1 Using default strategy strings 57 7 3 2 Mapping strategy strings 58 7 3 3 Graph bipartitioning strategy strings 59 7 3 4 Ordering strategy strings 63 7 3 5 Node separation strategy stri...

Page 4: ...erLoad 91 7 7 5 SCOTCH graphOrderSave 92 7 7 6 SCOTCH graphOrderSaveMap 92 7 7 7 SCOTCH graphOrderSaveTree 93 7 7 8 SCOTCH graphOrderCheck 93 7 7 9 SCOTCH graphOrderCompute 94 7 7 10 SCOTCH graphOrder...

Page 5: ...SCOTCH meshGeomLoadHabo 118 7 11 10SCOTCH meshGeomLoadScot 118 7 11 11SCOTCH meshGeomSaveScot 119 7 12 Error handling routines 120 7 12 1 SCOTCH errorPrint 120 7 12 2 SCOTCH errorPrintW 120 7 12 3 SC...

Page 6: ...reasonable time including the development of specific algorithms for common topologies such as the hypercube 11 21 When the target machine is assumed to have a communication network in the shape of a...

Page 7: ...of the Dual Recursive Bipartitioning or DRB mapping algorithm and in the study of several graph bipartitioning heuristics 41 all of which have been implemented in the Scotch software package 45 Then i...

Page 8: ...mitted on the channel respectively The target machine onto which is mapped the parallel program is also modeled by a valuated unoriented graph T called target graph or architecture graph Vertices vT a...

Page 9: ...ping and map the load imbalance ratio as map def P vS V S wS vS P vT V T wT vT and map def P vT V T 1 wT vT P vS V S S T vS vT wS vS map P vS V S wS vS However since the maximum load imbalance ratio i...

Page 10: ...ns Since domains may not be convex nor connected this distance may be estimated However it must respect certain homogeneity properties such as giving more accurate results as domain sizes decrease The...

Page 11: ...iated with domain D between the two subdomains D0 and D1 of D Dotted edges are of dilation zero their two ends being mapped onto the same subdomain Thin edges are cocycle edges 3 1 5 Execution scheme...

Page 12: ...ny type of graph bipartitioning method compatible with our criteria for quality Bipartitioning jobs maintain an in ternal image of the current bipartition indicating for every vertex of the job whethe...

Page 13: ...n is se lected first This method is used in post processing of other methods when load balance is mandatory For weighted graphs the strict enforcement of load balance may cause the swapping of isolate...

Page 14: ...mes in order to explore mostly in a gradient like fashion different areas of the solution space and the best partition found is kept Multi level This algorithm which has been studied by several author...

Page 15: ...symmetric reordering This reordering is chosen in such a way that pivoting down the diagonal in order on the resulting permuted matrix PAPT produces much less fill in and work than computing the fact...

Page 16: ...t has a partial visibility of the neighborhood of the subgraph Second the minimum degree algorithm returns the assembly tree that it computes for each subgraph thus allowing for supervariable amalgama...

Page 17: ...in and operation count This method also implements amalgamation techniques that result in efficient block computa tions in the factoring and the solving processes Halo approximate minimum fill The hal...

Page 18: ...ersion of the edge oriented multi level algorithm described in page 14 Thinner This greedy algorithm refines the current separator by removing all of the exceeding vertices that is vertices that do no...

Page 19: ...erefore the overall number of edge data is twice the number of edges Since version 3 3 has been introduced a new file format referred to as the new style file format which replaces the previous old st...

Page 20: ...which usually end in msh describe valuated meshes made of elements and nodes the elements of which can be mapped onto target architectures and the nodes of which can be reordered Meshes are bipartite...

Page 21: ...val This header data is then followed by as many lines as there are node and element vertices in the graph These lines are similar to the ones of the graph format except that in order to save disk spa...

Page 22: ...are vertices in the associated graph or mesh file only coordinates the labels of which match labels of graph or mesh vertices will be taken into account This feature allows all subgraphs of a given gr...

Page 23: ...there are processors Each of these lines holds three numbers the processor label the processor weight that is an estimation of its computational power and its terminal number The terminal number asso...

Page 24: ...elements while the upper lev els of the tree model interconnection networks intra chip buses inter chip interconnection networks network routers etc as shown in Figure 8 The communication cost betwee...

Page 25: ...1 and the two subdomains of any domain i are labeled 2i and 2i 1 The distance between any two subdomains i and j is 0 if i j and 1 else varhcub Defines a variable sized hypercube Domains are labeled s...

Page 26: ...he source graph or mesh The structure of ordering files is analogous to the one of mapping files they differ only by the meaning of their data Ordering files begin with the number of ordering lines wh...

Page 27: ...t decomposition defined target files and especially to turn a source graph file into a target file The mapping and ordering programs themselves Output handling programs which are the mapping performan...

Page 28: ...xternal mesh file mmk_ gmk_ mcv xyz Geometry file gord gmk_msh file ord Ordering file Mapping map gmtst file Graphics gout amk_grf gotst acpl amk_ gmap Data flow Figure 12 General architecture of the...

Page 29: ...ormat the stream is assumed to be compressed according to the corresponding format A filter task will then be used to process it accordingly if the format is implemented in Scotch and enabled on your...

Page 30: ...te way between algorithmically coded built in target architectures and decompositions computed by mapping with amk grf Like built in target architectures their decompositions are algorithmically compu...

Page 31: ...of a multi user parallel machine As a matter of fact if the yet unallocated part of the machine is represented by a source graph with n vertices and n processors are requested by a user in order to ru...

Page 32: ...the context of multi user parallel ma chines On these machines when users request processors in order to run their jobs the partitions allocated by the operating system may not be regular nor connect...

Page 33: ...le whenever geometry data is available At the time being it accepts four input formats the Matrix Market format 5 the Harwell Boeing col lection format 10 the Chaco MeTiS graph format 24 and the Scotc...

Page 34: ...s Avail able bipartitioning methods include a multi level algorithm that uses other bipartitioning methods to compute the initial and refined bipartitions an improved implementation of the Fiduccia Ma...

Page 35: ...mapping strategy strat The format of mapping strategies is de fined in section 7 3 2 This option is incompatible with options b and c sobj Mask source edge and vertex weights This option allows the u...

Page 36: ...is labeled posY dimX posX Program gmk m3 outputs the source file of a tridimensional mesh with dimZ layers of dimY rows by dimX columns If the t option is set tori are built instead of meshes The vert...

Page 37: ...f messages that have to be sent to exchange data between all neighboring blocks The second communication line gives the average dilation of the edges followed by the sum of all edge dilations The thir...

Page 38: ...he graphs to order are very large the same results can be obtained by using the dgord parallel program of the PT Scotch distribution which can read centralized graph files too Options Since the progra...

Page 39: ...following switches s Strategy information This parameter displays the ordering strategy which will be used by gord t Timing information 6 3 11 gotst Synopsis gotst input graph file input ordering file...

Page 40: ...e result of the mapping of a subgraph of the bidimensional mesh M2 4 4 onto the complete graph K 2 can be displayed on the whole M2 4 4 graph and Figure 14 c shows how the display of the same mapping...

Page 41: ...for display by the ivview program 40 The optional pa rameters are given below c Color output using 16 different colors Opposite of g g Grey level output using 8 different levels Opposite of c r Remov...

Page 42: ...output suitable for direct printing Oppo site of e g Grey level PostScript output Opposite of c l Large clipping Mapping disks are included in the clipping area computation Opposite of s r Remove cut...

Page 43: ...geometry file options Description The program mcv is the source mesh converter It takes on input a mesh file of the format specified with the i option and outputs its equivalent in the format specifie...

Page 44: ...m3 outputs the source file of a tridimensional mesh with dimX dimY dimZ elements and dimX 1 dimY 1 dimZ 1 nodes Options goutput geometry file Output mesh geometry to file output geometry file for mmk...

Page 45: ...he mapping of mesh node vertices to col umn blocks All of the separators and leaves produced by the nested dissection method are considered as distinct column blocks which may be in turn split by the...

Page 46: ...s and element and node degrees Options h Display the program synopsis V Print the program version and copyright 7 Library All of the features provided by the programs of the Scotch distribution may be...

Page 47: ...from a stream and so on Typically functions that return an error code return zero if the function suc ceeds and a non zero value in case of error For instance the SCOTCH graphInit and SCOTCH graphLoad...

Page 48: ...called PXFFILENO in the normalized POSIX Fortran API and files which use it should include the USE IFPOSIX direc tive whenever necessary An alternate non normalized function also exists in most Unix...

Page 49: ...for all graph related values in accordance to the size of the SCOTCH Num type as set by the DINTSIZEx compilation flags Also the INTEGER idx type represents an integer type of a size equivalent to the...

Page 50: ...aph is twice the number of graph edges verttab Array of start indices in edgetab of vertex adjacency sub arrays vendtab Array of after last indices in edgetab of vertex adjacency sub arrays For any ve...

Page 51: ...s bold numbers close to vertices are vertex loads and numbers close to edges are edge loads Since the edge array is compact verttab is of size vertnbr 1 and vendtab points to verttab 1 edgetab verttab...

Page 52: ...he adjacencies of its neighbor vertices must also be updated to account for it If free space had been reserved at the end of each of the neighbors one just has to increment the vendtab i values of eve...

Page 53: ...er verttab baseval baseval and verttab baseval vertnbr baseval edgenbr velotab Array of size vertnbr holding the integer load associated with each vertex As for graphs it is possible to handle elegant...

Page 54: ...de of a single array of double precision values which represent the coordinates of the vertices of a graph or of the node vertices of a mesh in vertex order The fields of a geometry structure are the...

Page 55: ...hing of the mesh of Figure 19 New node vertices have been added at the end of the vertex sub array new elements have been added at the beginning of the element sub array and vertex base values have be...

Page 56: ...ber of column blocks that is supervariables in the block ordering rangtab Array of ranges for the column blocks Column block c with baseval c cblknbr baseval contains columns with indices ranging from...

Page 57: ...s is without further parametrization this object will be filled with a default strategy when passing it as a parameter to the next partitioning or ordering routine to be called On return the strategy...

Page 58: ...1 0 Coars ening stops when either the coarsening ratio is above the maximum coars ening ratio or the graph has fewer vertices than the minimum number of vertices allowed type type Set the type of matc...

Page 59: ...strings A graph bipartitioning strategy is made of one or several graph bipartitioning meth ods which can be combined by means of strategy operators Strategy operators are listed below by increasing...

Page 60: ...rated by commas and the whole list be enclosed between curly braces The currently available graph bipartitioning methods are the following b Band method This method builds a band graph of given width...

Page 61: ...dif and rem parameters must be equal to 1 but in order to speed up the diffusion process other combi nations of higher sum can be tried In this case the number of passes must be kept low to avoid num...

Page 62: ...sed low strat Set the strategy that is used to compute the partition of the coarsest graph at the lowest level of the coarsening process rat rat Set the threshold maximum coarsening ratio over which g...

Page 63: ...cond1 and cond2 are true cond Logical not operator The result of the condition is true only if cond is false var relop val Relational operator where var is a node variable val is either a node variab...

Page 64: ...n computed c Compression method 2 The parameters of the compression method are listed below rat rat Set the compression ratio over which graphs and meshes will not be compressed Useful values range be...

Page 65: ...nt of extra diagonal blocks If the number of extra diagonal blocks is not relevant the s method should be preferred This method has only one parameter pass nbr Set the number of sweeps performed by th...

Page 66: ...used should compute an initial separation from scratch and every following method should use the result of the previous one as a starting point strat Grouping operator The strategy enclosed within th...

Page 67: ...lgorithms in a multi level context but it improves partition quality too The parameters of the band separation method are listed below bnd strat Set the vertex separation strategy to be used on the ba...

Page 68: ...ccia Mattheyses algorithm repeatedly moves vertices from the separator to any of the two parts so as to minimize the size of the separator A pass completes either when all of the vertices have been mo...

Page 69: ...ccia Mattheyses algorithm with move 0 v Mesh to graph method Available only for mesh separation strategies From the mesh to which this method applies is derived a graph such that a graph vertex is ass...

Page 70: ...al structures Return values SCOTCH archInit returns 0 if the graph structure has been successfully ini tialized and 1 else 7 4 2 SCOTCH archExit Synopsis void SCOTCH archExit SCOTCH Arch archptr scotc...

Page 71: ...eprecision archdat integer fildes integer ierr Description The SCOTCH archSave routine saves the contents of the SCOTCH Arch structure pointed to by archptr to stream stream in the Scotch target archi...

Page 72: ...e function returns the number of nodes of the given tar get architecture The Fortran routine has a second parameter of integer type which is set on return with the number of nodes of the target archit...

Page 73: ...rchitecture from source graphs available at page 32 Return values SCOTCH archBuild returns 0 if the decomposition defined architecture has been successfully computed and 1 else 7 4 8 SCOTCH archCmplt...

Page 74: ...archptr const SCOTCH Num hdimval scotchfarchhcub doubleprecision archdat integer num hdimval integer ierr Description The SCOTCH archHcub routine fills the SCOTCH Arch structure pointed to by archptr...

Page 75: ...dimval ydimval zdimval processors Return values SCOTCH archMesh3D returns 0 if the 3D mesh target architecture has been successfully built and 1 else 7 4 13 SCOTCH archTleaf Synopsis int SCOTCH archTl...

Page 76: ...r Description The SCOTCH archTorus2D routine fills the SCOTCH Arch structure pointed to by archptr with the description of a 2D torus architecture with xdimval ydimval processors Return values SCOTCH...

Page 77: ...no longer of use call function SCOTCH graphExit to free its internal structures Return values SCOTCH graphInit returns 0 if the graph structure has been successfully ini tialized and 1 else 7 5 2 SCO...

Page 78: ...ng of source graph files by programs written in C as well as in Fortran the base value of the graph to read can be set to 0 or 1 by setting the baseval parameter to the proper value A value of 1 indic...

Page 79: ...it of the graph file Return values SCOTCH graphSave returns 0 if the graph structure has been successfully writ ten to stream and 1 else 7 5 6 SCOTCH graphBuild Synopsis int SCOTCH graphBuild SCOTCH G...

Page 80: ...elds makes them be considered as missing arrays The same holds for edlotab when it is passed a reference equal to edgetab Setting vendtab to refer to one cell after verttab yields the same result as i...

Page 81: ...ven SCOTCH Graph structure It can be used in client applications to determine if a graph that has been created from used generated data by means of the SCOTCH graphBuild routine is consistent prior to...

Page 82: ...dx integer num edgenbr integer idx edgeidx integer num edloidx Description The SCOTCH graphData routine is the dual of the SCOTCH graphBuild routine It is a multiple accessor that returns scalar value...

Page 83: ...do not exist For instance if some base array myarray 1 is passed as parameter indxtab then the first cell of array verttab will be accessible as myarray vertidx In order for this feature to behave pr...

Page 84: ...ly degrmin degrmax degravg and degrdlt are the minimum ver tex degree the maximum vertex degree the average vertex degree and the variance of the vertex degrees respectively edlomin edlomax edlosum ed...

Page 85: ...onst SCOTCH Strat straptr SCOTCH Num parttab scotchfgraphmap doubleprecision grafdat doubleprecision archdat doubleprecision stradat integer num parttab integer ierr Description The SCOTCH graphMap ro...

Page 86: ...by grafptr and which will receive the indices of the vertices of the target architecture pointed to by archptr It should be the first function to be called upon a SCOTCH Mapping structure When the map...

Page 87: ...OTCH graphMapLoad returns 0 if the mapping structure has been success fully loaded from stream and 1 else 7 6 6 SCOTCH graphMapSave Synopsis int SCOTCH graphMapSave const SCOTCH Graph grafptr const SC...

Page 88: ...values SCOTCH graphMapCompute returns 0 if the mapping has been successfully com puted and 1 else In this latter case the mapping array may however have been partially or completely filled but its con...

Page 89: ...ure pointed to by grafptr using the ordering strategy pointed to by stratptr and returns ordering data in the scalar pointed to by cblkptr and the four arrays permtab peritab rangtab and treetab The p...

Page 90: ...ly filled but their contents are not significant 7 7 2 SCOTCH graphOrderInit Synopsis int SCOTCH graphOrderInit const SCOTCH Graph grafptr SCOTCH Ordering ordeptr SCOTCH Num permtab SCOTCH Num peritab...

Page 91: ...erexit doubleprecision grafdat doubleprecision ordedat Description The SCOTCH graphOrderExit function frees the contents of a SCOTCH Ordering structure previously initialized by SCOTCH graphOrderInit...

Page 92: ...nix file descriptor fildes associated with the logical unit of the ordering file Return values SCOTCH graphOrderSave returns 0 if the ordering structure has been success fully written to stream and 1...

Page 93: ...sociated with the SCOTCH Ordering structure pointed to by ordeptr to stream stream The format of the tree output file resembles the one of a mapping or ordering file it is made up of as many lines as...

Page 94: ...rategy pointed to by stratptr and stores its result in the ordering structure pointed to by ordeptr On return the ordering structure holds a block ordering of the given graph see section 7 7 2 for a d...

Page 95: ...n induced ver tex are ordered consecutively with the highest available indices Conse quently the permuted indices of induced vertices range from baseval to listnbr baseval 1 while the permuted indices...

Page 96: ...num baseval integer ierr Description The SCOTCH meshLoad routine fills the SCOTCH Mesh structure pointed to by meshptr with the source mesh description available from stream stream in the Scotch mesh...

Page 97: ...tions to obtain the number of the Unix file descriptor fildes associated with the logical unit of the mesh file Return values SCOTCH meshSave returns 0 if the mesh structure has been successfully writ...

Page 98: ...ltab is the vertex label array of size velmnbr vnodnbr if it exists edgenbr is the number of arcs that is twice the number of edges edgetab is the adjacency array of size at least edgenbr it can be mo...

Page 99: ...nsistent prior to calling any other routines of the libScotch library Return values SCOTCH meshCheck returns 0 if mesh data are consistent and 1 else 7 8 7 SCOTCH meshSize Synopsis void SCOTCH meshSiz...

Page 100: ...vertidx integer idx vendidx integer idx veloidx integer idx vnloidx integer idx vlblidx integer num edgenbr integer idx edgeidx integer num degrmax Description The SCOTCH meshData routine is the dual...

Page 101: ...y indices are computed Therefore instead of returning references the routine returns integers which represent the starting index of each of the relevant arrays with respect to the base input array or...

Page 102: ...x degree the average element vertex degree and the variance of the element vertex degrees respectively ndegmin ndegmax ndegavg and ndegdlt are the minimum element vertex degree the maximum element ver...

Page 103: ...um rangtab SCOTCH Num treetab scotchfmeshorder doubleprecision meshdat doubleprecision stradat integer num permtab integer num peritab integer num cblknbr integer num rangtab integer num treetab integ...

Page 104: ...number of column blocks of the produced ordering and rangtab holds the starting indices of each of the permuted column blocks in increasing order so that column block i starts at index rangtab i and e...

Page 105: ...OTCH meshOrderInit routine should be the first function to be called upon a SCOTCH Ordering structure for ordering meshes When the ordering structure is no longer of use the SCOTCH meshOrderExit funct...

Page 106: ...ed to by ordeptr to stream stream in the Scotch mapping format see section 5 5 A target domain number is associated with every block such that all node vertices belonging to the same block are shown a...

Page 107: ...fildes associated with the logical unit of the tree mapping file Return values SCOTCH meshOrderSaveTreereturns 0 if the separators tree structure has been successfully written to stream and 1 else 7 9...

Page 108: ...it SCOTCH Strat straptr scotchfstratinit doubleprecision stradat integer ierr Description The SCOTCH stratInit function initializes a SCOTCH Strat structure so as to make it suitable for future operat...

Page 109: ...h the logical unit of the output file Return values SCOTCH stratSave returns 0 if the strategy string has been successfully writ ten to stream and 1 else 7 10 4 SCOTCH stratGraphBipart Synopsis int SC...

Page 110: ...lse 7 10 6 SCOTCH stratGraphMapBuild Synopsis int SCOTCH stratGraphMapBuild SCOTCH Strat straptr const SCOTCH Num flagval const SCOTCH Num partnbr const double balrat scotchfstratgraphmapbuild doublep...

Page 111: ...s been successfully set and 1 else 7 10 8 SCOTCH stratGraphOrderBuild Synopsis int SCOTCH stratGraphOrderBuild SCOTCH Strat straptr const SCOTCH Num flagval const double balrat scotchfstratgraphorderb...

Page 112: ...successfully set and 1 else 7 10 10 SCOTCH stratMeshOrderBuild Synopsis int SCOTCH stratMeshOrderBuild SCOTCH Strat straptr const SCOTCH Num flagval const double balrat scotchfstratmeshorderbuild dou...

Page 113: ...utines to be able to read their data on the fly from streams that can only be read once such as communication pipes Having both aspects taken into account in a single call makes the writing of file co...

Page 114: ...ta will be written Since there are no pointers in Fortran a specific mechanism is used to allow users to access the coordinate array The scotchfgeomdata routine is passed an integer array the first el...

Page 115: ...andle geometry data the geomptr and geomstream fields are not used as well as the string field Fortran users must use the PXFFILENO or FNUM functions to obtain the number of the Unix file descriptor g...

Page 116: ...geomdat integer graffildes integer geomfildes character string Description The SCOTCH graphGeomLoadHabo routine fills the SCOTCH Graph structure pointed to by grafptr with the source graph description...

Page 117: ...e Unix file descriptors graffildes and geomfildes associated with the logical units of the graph and geometry files Return values SCOTCH graphGeomLoadScot returns 0 if the graph topology and geometry...

Page 118: ...the source mesh description available from stream meshstream in the Harwell Boeing square elemental matrix format 10 Since this mesh format does not handle geometry data the geomptr and geom stream fi...

Page 119: ...nd filled with the data read and 1 else 7 11 11 SCOTCH meshGeomSaveScot Synopsis int SCOTCH meshGeomSaveScot const SCOTCH Mesh meshptr const SCOTCH Geom geomptr FILE meshstream FILE geomstream const c...

Page 120: ...s function has returned In order to free the user from the burden of writing a basic error handler from scratch the libscotcherr a library provides error routines that print error messages on the stan...

Page 121: ...y to compute the results 7 14 MeTiS compatibility library The MeTiS compatibility library provides stubs which redirect some calls to MeTiS routines to the corresponding Scotch counterparts In order t...

Page 122: ...d METIS NodeWND call the same Scotch routine which uses the Scotch default ordering strategy proved to be efficient in most cases 7 14 2 METIS NodeND Synopsis void METIS NodeND const int const n const...

Page 123: ...flag integer options integer perm integer iperm Description The METIS NodeWND function performs a nested dissection ordering of the graph passed as arrays xadj adjncy and vwgt using the default Scotch...

Page 124: ...of the graph represented by arrays xadj adjncy vwgt and adjwgt using the default Scotch mapping strategy The options array is not used The part array has the same meaning as the parttab array of Scot...

Page 125: ...essing which increases running time to a small extent All of the three MeTiS stubs METIS PartGraphKway METIS PartGraph Recursive and METIS PartGraphVKway call the same Scotch routine which uses the Sc...

Page 126: ...efficient in most cases 8 Installation Version 5 1 of the Scotch software package is distributed as free libre software under the CeCILL C free libre software license 6 which is very similar to the GN...

Page 127: ...I conflicts the MeTiS compatibility library will not be usable It is usually safer and cleaner to tune your C and Fortran compilers to make them inter pret int and INTEGER types as 32 or 64 bit values...

Page 128: ...map gmk m2 32 32 gmap tgt h8 tgt tmp brol map Build the Open Inventor file graph iv that contains the display of a source graph the source and geometry files of which are named graph grf and graph xyz...

Page 129: ...tion must be placed before the lmetis one so that routines that are redefined by Scotch are selected instead of their MeTiS counterpart When no other MeTiS routines than the ones re defined by Scotch...

Page 130: ...while refinement meth ods must be provided an existing partition to improve In addition to the topological description of the underlying graph the working graph and mesh structures comprise variables...

Page 131: ...stands for strat egy First edit vgraph separate st h In the VgraphSeparateStMethodType enumeration add a line for your new method VGRAPHSEPASTMETHXY Then edit vgraph separate st c where all of the re...

Page 132: ...rder c since it is the graph ordering routine which makes use of graph vertex separation methods to compute separators for the nested dissection ordering method 10 4 Licensing of new methods and of de...

Page 133: ...ngton The Matrix Market exchange formats initial design NISTIR 5935 National Institute of Standards and Technology December 1996 6 CeCILL CEA CNRS INRIA Logiciel Libre free libre software license Avai...

Page 134: ...hms for sparse matrix factorization IEEE Trans Parallel Distrib Syst 8 5 502 520 1997 21 S W Hammond Mapping unstructured grid computations to massively parallel computers PhD thesis Rensselaer Polyte...

Page 135: ...ptember 1998 35 B W Kernighan and S Lin An efficient heuristic procedure for partitionning graphs BELL System Technical Journal pages 291 307 February 1970 36 M Laguna T A Feo and H C Elrod A greedy r...

Page 136: ...e matrices with eigenvectors of graphs SIAM Journal of Matrix Analysis 11 3 430 452 July 1990 50 E Rothberg Performance of panel and block approaches to sparse Cholesky factorization on the iPSC 860 a...