1 | |
---|
2 | METIS 4.0.1, 11/29/98 |
---|
3 | ------------------------------------------------------------------------------ |
---|
4 | This is mostly a bug-fix release |
---|
5 | |
---|
6 | - Fixed some bugs in the multi-constraint partitioning routines |
---|
7 | - Fixed some bugs in the volume-minimization routines |
---|
8 | |
---|
9 | |
---|
10 | |
---|
11 | METIS 4.0.0, 9/20/98 |
---|
12 | ------------------------------------------------------------------------------ |
---|
13 | METIS 4.0 contains a number of changes over the previous major release (ver |
---|
14 | 3.0.x). Most of these changes are concentrated on the graph and mesh |
---|
15 | partitioning routines and they do not affect the sparse matrix re-ordering |
---|
16 | routines. Here is a list of the major changes: |
---|
17 | |
---|
18 | Multi-Constraint Partitioning |
---|
19 | ----------------------------- |
---|
20 | METIS now includes partitioning routines that can be used to a partition |
---|
21 | a graph in the presence of multiple balancing constraints. |
---|
22 | |
---|
23 | Minimizing the Total Communication Volume |
---|
24 | ----------------------------------------- |
---|
25 | METIS now includes partitioning routines whose objective is to minimize |
---|
26 | the total communication volume (as opposed to minimizing the edge-cut). |
---|
27 | |
---|
28 | Minimizing the Maximum Connectivity of the Subdomains |
---|
29 | ----------------------------------------------------- |
---|
30 | The k-way partitioning routines in METIS can now directly minimize the number |
---|
31 | of adjacent subdomains. For most graphs corresponding to finite element |
---|
32 | meshes, METIS is able to significantly reduce the maximum (and total) number of |
---|
33 | adjacent subdomains. |
---|
34 | |
---|
35 | |
---|
36 | |
---|
37 | |
---|
38 | METIS 3.0.6, 1/28/98 |
---|
39 | ------------------------------------------------------------------------------- |
---|
40 | - Fixed some problems when too many partitions were asked, and each partition |
---|
41 | end up having 0 vertices |
---|
42 | - Fixed some bugs in the I/O routines |
---|
43 | - Added support for the g77 compiler under Linux |
---|
44 | |
---|
45 | |
---|
46 | METIS 3.0.5, 12/22/97 |
---|
47 | ------------------------------------------------------------------------------- |
---|
48 | - Fixed problems on 64-bit architectures (eg., -64 option on SGIs). |
---|
49 | - Added some options in Makefile.in |
---|
50 | |
---|
51 | |
---|
52 | METIS 3.0.4, 12/1/97 |
---|
53 | ------------------------------------------------------------------------------- |
---|
54 | Fixed a memory leak in the ordering code. |
---|
55 | |
---|
56 | |
---|
57 | METIS 3.0.3, 11/5/97 |
---|
58 | ------------------------------------------------------------------------------- |
---|
59 | This is mostly a bug-fix release with just a few additions |
---|
60 | |
---|
61 | Added functionality |
---|
62 | - Added support for quadrilateral elements. |
---|
63 | - Added a routine METIS_EstimateMemory that estimates the amount of |
---|
64 | memory that will be allocated by METIS. This is useful in determining |
---|
65 | if a problem can run on your system. |
---|
66 | - Added hooks to allow PARMETIS to use the orderings produced by METIS. |
---|
67 | This is hidden from the user but it will be used in the next release |
---|
68 | of PARMETIS. |
---|
69 | |
---|
70 | Bug-fixes |
---|
71 | - Fixed a bug related to memory allocation. This should somewhat reduce the |
---|
72 | overall memory used by METIS. |
---|
73 | - Fixed some bugs in the 'graphchk' program in the case of weighted graphs. |
---|
74 | - Removed some code corresponding to unused options. |
---|
75 | - Fixed some minor bugs in the node-refinement code |
---|
76 | |
---|
77 | |
---|
78 | |
---|
79 | ------------------------------------------------------------------------------- |
---|
80 | METIS 3.0 contains a number of changes over METIS 2.0. |
---|
81 | The major changes are the following: |
---|
82 | |
---|
83 | General Changes |
---|
84 | --------------- |
---|
85 | 1. Added code to directly partition finite element meshes. |
---|
86 | |
---|
87 | 2. Added code to convert finite element meshes into graphs so they |
---|
88 | can be used by METIS. |
---|
89 | |
---|
90 | 1. The names, calling sequences, and options of the routines in |
---|
91 | METISlib have been changed. |
---|
92 | |
---|
93 | 2. Better support has been added for Fortran programs. |
---|
94 | |
---|
95 | 3. Eliminated the 'metis' program. The only way to tune METIS's |
---|
96 | behavior is to use METISlib. |
---|
97 | |
---|
98 | 4. Improved memory management. METIS should now only abort if truly |
---|
99 | there is no more memory left in the system. |
---|
100 | |
---|
101 | |
---|
102 | Graph Partitioning |
---|
103 | ------------------ |
---|
104 | 1. Added partitioning routines that can be used to compute a partition |
---|
105 | with prescribed partition weights. For example, they can be used to |
---|
106 | compute a 3-way partition such that partition 1 has 50% of the weight, |
---|
107 | partition 2 has 20% of the way, and partition 3 has 30% of the weight. |
---|
108 | |
---|
109 | 2. Improved the speed of the k-way partitioning algorithm (kmetis). The |
---|
110 | new code has better cache locality which dramatically improves the |
---|
111 | speed for large graphs. A factor of 4 speedup can be obtained for |
---|
112 | certain graphs. METIS can now partition a 4 million node graph |
---|
113 | in well under a minute on a MIPS R10000. |
---|
114 | |
---|
115 | 3. Eliminated some of the options that were seldom used. |
---|
116 | |
---|
117 | |
---|
118 | Fill-Reducing Orderings |
---|
119 | ---------------------- |
---|
120 | 1. Added a node based ordering code `onmetis' that greatly improves |
---|
121 | ordering quality. |
---|
122 | |
---|
123 | 2. Improved the quality of the orderings produced by the original |
---|
124 | edge-based ordering code (it is now called 'oemetis'). |
---|
125 | |
---|
126 | 3. METIS can now analyze the graph and try to compress together |
---|
127 | nodes with identical sparsity pattern. For some problems, this |
---|
128 | significantly reduces ordering time |
---|
129 | |
---|
130 | 4. METIS can now prune dense columns prior to ordering. This can be |
---|
131 | helpful for LP matrices. |
---|
132 | |
---|
133 | |
---|
134 | Mesh Partitioning |
---|
135 | ----------------- |
---|
136 | 1. METIS can now directly partition the element node array of finite |
---|
137 | element meshes. It produces two partitioning vectors. One for the |
---|
138 | elements and one for the nodes. METIS supports the following |
---|
139 | elements: triangles, tetrahedra, hexahedra |
---|
140 | |
---|
141 | |
---|
142 | Mesh-To-Graph Conversion Routines |
---|
143 | --------------------------------- |
---|
144 | 1. METIS now includes a number of mesh conversion functions that can |
---|
145 | be used to create the dual and nodal graphs directly from the |
---|
146 | element connectivity arrays. These are highly optimized routines. |
---|
147 | |
---|
148 | |
---|
149 | |
---|