Debian Codegraph @

metis/Changelog

raw
1
2 metis-5.1.0
3 ------------------------------------------------------------------------
4 r13937 | karypis | 2013-03-29 23:08:21 -0500 (Fri, 29 Mar 2013)
5
6 - Further extended the 2-hop coarsening scheme introduced in 5.0.2 for
7 for graphs with highly variable degree distribution (e.g., power-law).
8 This coarsening scheme is automatically used when the standard
9 1-hop-based scheme leaves a large fraction of the vertices of the
10 graph unmatched. It leads to better quality partitionings, lower
11 memory utilization, and faster execution time. In principle, this
12 scheme will never be triggered for graphs/matrices appearing in
13 scientific computations derived from FE meshes. However, if you
14 notice that the quality of the solutions is significantly worse,
15 this 2-hop matching can be turned off by using the '-no2hop' command
16 line option and the associated options[] parameter (as described
17 in the manual).
18 - Fixed 0/1 numbering issue with mesh partitioning routines (flyspray
19 issue #109)
20
21
22 metis-5.0.3
23 ------------------------------------------------------------------------
24 r13822 | karypis | 2013-03-11 14:40:11 -0500 (Mon, 11 Mar 2013)
25
26 - Fixed the bug that was introduced in 5.x for creating nodal graphs
27 from meshes (flyspray issue #107).
28 - Changed the license to Apache Version 2.
29
30
31 metis-5.0.2
32 ------------------------------------------------------------------------
33 r10974 | karypis | 2011-10-29 18:24:32 -0500 (Sat, 29 Oct 2011)
34
35 - Fixed issue with high-degree vertices and mask-based compression.
36 - Fixed issue with wrong COARSENING_FRACTION.
37 - Modified coarsening schemes to better support non FE graphs.
38
39
40 metis-5.0.1
41 ------------------------------------------------------------------------
42 r10709 | karypis | 2011-08-31 16:07:57 -0500 (Wed, 31 Aug 2011)
43
44 - Fixed critical bug in the mesh partitioning routines.
45
46
47 metis-5.0
48 ------------------------------------------------------------------------
49 r10667 | karypis | 2011-08-04 00:35:30 -0500 (Thu, 04 Aug 2011)
50
51 - Updated/corrected error messages.
52 - Addressed some build issues.
53
54
55 metis-5.0rc3
56 ------------------------------------------------------------------------
57 r10560 | karypis | 2011-07-13 08:19:10 -0500 (Wed, 13 Jul 2011)
58
59 - Fixed various bugs that were identified by testers.
60 - Some minor performance and quality improvements.
61 - Addressed some build issues.
62
63
64 metis-5.0rc2
65 ------------------------------------------------------------------------
66 r10496 | karypis | 2011-07-06 11:04:45 -0500 (Wed, 06 Jul 2011)
67
68 - Various run-time and quality optimizations.
69 - Option error-checking.
70 - Signal-based heap cleanup on error. Metis API routines will not
71 return nicely and cleanup all memory that may have allocated.
72 - Reduced memory requirements.
73 - Fixed various bugs identified in rc1.
74 - Added back Fortran support in the form of alternate API names
75 (see libmetis/frename.h).
76 - Minor code changes to accommodate ParMetis 4.0.
77
78
79 metis-5.0rc1
80 ------------------------------------------------------------------------
81 r10227 | karypis | 2011-06-13 23:35:05 -0500 (Mon, 13 Jun 2011)
82
83 - A nearly complete re-write of Metis' code-based that changed expanded
84 the functionality of the command-line programs and API routines.
85 - Multi-constraint partitioning can be used in conjunction with
86 minimization of the total communication volume.
87 - All graph and mesh partitioning routines take as input the target
88 sizes of the partitions, which among others, allow them to compute
89 partitioning solutions that are well-suited for parallel architectures
90 with heterogeneous computing capabilities.
91 - When multi-constraint partitioning is used, the target sizes of the
92 partitions are specified on a per partition-constraint pair.
93 - The multilevel k-way partitioning algorithms can compute a
94 partitioning solution in which each partition is contiguous.
95 - All partitioning and ordering routines can compute multiple different
96 solutions and select the best as the final solution.
97 - The mesh partitioning and mesh-to-graph conversion routines can
98 operate on mixed element meshes.
99 - The command-line programs provide full access to the entire set of
100 capabilities provided by Metis' API.
101 - Re-written the memory management subsystem to reduce overall memory
102 requirements.
103
104
105
106 metis-5.0pre2
107 ------------------------------------------------------------------------
108 r1437 | karypis | 2007-04-07 23:16:16 -0500 (Sat, 07 Apr 2007)
109
110 - Added installation instructions and change-logs.
111 - Tested 32bit & 64bit on 64bit architectures and passed tests.
112 - Tested 32bit on 32bit architectures and passed tests.
113 - strtoidx() addition for portable input file parsing
114 - Restructured the internal memory allocation schemes for graph and
115 refinement data. This should enhance portability and make the code
116 easier to maintain.
117 - Fixed some bad memory allocation calls (i.e., sizeof(x)/sizeof(idxtype).
118 However, there are tons of those and need to be corrected once and for
119 all by eliminating workspace and the associated mallocs.
120 - Added mprint/mscanf family of functions for portable formated I/O
121 of the idxtype datatype. The specifier for this datatype is %D.
122 All library routines use this function for printing.
123 The implementation of these routines is not very efficient, but
124 that should do for now (in principle these routines should not be
125 used unless debugging).
126 - Incorporated GKlib into METIS, which replaced many of its internal
127 functions. GKlib's malloc interface will enable graceful and clean
128 aborts (i.e., free all internally allocated memory) on fatal errors.
129 This will probably be available in the next pre-release.
130 - Fixed the problems associated with metis.h that were identified by
131 David (flyspray Issue #9).
132
133
134 METIS 4.0.2, 3/10/04
135 ------------------------------------------------------------------------------
136 - Fixed a problem with weighted graphs and ometis.c
137
138
139 METIS 4.0.1, 11/29/98
140 ------------------------------------------------------------------------------
141 This is mostly a bug-fix release
142
143 - Fixed some bugs in the multi-constraint partitioning routines
144 - Fixed some bugs in the volume-minimization routines
145
146
147
148 METIS 4.0.0, 9/20/98
149 ------------------------------------------------------------------------------
150 METIS 4.0 contains a number of changes over the previous major release (ver
151 3.0.x). Most of these changes are concentrated on the graph and mesh
152 partitioning routines and they do not affect the sparse matrix re-ordering
153 routines. Here is a list of the major changes:
154
155 Multi-Constraint Partitioning
156 -----------------------------
157 METIS now includes partitioning routines that can be used to a partition
158 a graph in the presence of multiple balancing constraints.
159
160 Minimizing the Total Communication Volume
161 -----------------------------------------
162 METIS now includes partitioning routines whose objective is to minimize
163 the total communication volume (as opposed to minimizing the edge-cut).
164
165 Minimizing the Maximum Connectivity of the Subdomains
166 -----------------------------------------------------
167 The k-way partitioning routines in METIS can now directly minimize the number
168 of adjacent subdomains. For most graphs corresponding to finite element
169 meshes, METIS is able to significantly reduce the maximum (and total) number of
170 adjacent subdomains.
171
172
173
174
175 METIS 3.0.6, 1/28/98
176 -------------------------------------------------------------------------------
177 - Fixed some problems when too many partitions were asked, and each partition
178 end up having 0 vertices
179 - Fixed some bugs in the I/O routines
180 - Added support for the g77 compiler under Linux
181
182
183 METIS 3.0.5, 12/22/97
184 -------------------------------------------------------------------------------
185 - Fixed problems on 64-bit architectures (eg., -64 option on SGIs).
186 - Added some options in Makefile.in
187
188
189 METIS 3.0.4, 12/1/97
190 -------------------------------------------------------------------------------
191 Fixed a memory leak in the ordering code.
192
193
194 METIS 3.0.3, 11/5/97
195 -------------------------------------------------------------------------------
196 This is mostly a bug-fix release with just a few additions
197
198 Added functionality
199 - Added support for quadrilateral elements.
200 - Added a routine METIS_EstimateMemory that estimates the amount of
201 memory that will be allocated by METIS. This is useful in determining
202 if a problem can run on your system.
203 - Added hooks to allow PARMETIS to use the orderings produced by METIS.
204 This is hidden from the user but it will be used in the next release
205 of PARMETIS.
206
207 Bug-fixes
208 - Fixed a bug related to memory allocation. This should somewhat reduce the
209 overall memory used by METIS.
210 - Fixed some bugs in the 'graphchk' program in the case of weighted graphs.
211 - Removed some code corresponding to unused options.
212 - Fixed some minor bugs in the node-refinement code
213
214
215
216 -------------------------------------------------------------------------------
217 METIS 3.0 contains a number of changes over METIS 2.0.
218 The major changes are the following:
219
220 General Changes
221 ---------------
222 1. Added code to directly partition finite element meshes.
223
224 2. Added code to convert finite element meshes into graphs so they
225 can be used by METIS.
226
227 1. The names, calling sequences, and options of the routines in
228 METISlib have been changed.
229
230 2. Better support has been added for Fortran programs.
231
232 3. Eliminated the 'metis' program. The only way to tune METIS's
233 behavior is to use METISlib.
234
235 4. Improved memory management. METIS should now only abort if truly
236 there is no more memory left in the system.
237
238
239 Graph Partitioning
240 ------------------
241 1. Added partitioning routines that can be used to compute a partition
242 with prescribed partition weights. For example, they can be used to
243 compute a 3-way partition such that partition 1 has 50% of the weight,
244 partition 2 has 20% of the way, and partition 3 has 30% of the weight.
245
246 2. Improved the speed of the k-way partitioning algorithm (kmetis). The
247 new code has better cache locality which dramatically improves the
248 speed for large graphs. A factor of 4 speedup can be obtained for
249 certain graphs. METIS can now partition a 4 million node graph
250 in well under a minute on a MIPS R10000.
251
252 3. Eliminated some of the options that were seldom used.
253
254
255 Fill-Reducing Orderings
256 ----------------------
257 1. Added a node based ordering code `onmetis' that greatly improves
258 ordering quality.
259
260 2. Improved the quality of the orderings produced by the original
261 edge-based ordering code (it is now called 'oemetis').
262
263 3. METIS can now analyze the graph and try to compress together
264 nodes with identical sparsity pattern. For some problems, this
265 significantly reduces ordering time
266
267 4. METIS can now prune dense columns prior to ordering. This can be
268 helpful for LP matrices.
269
270
271 Mesh Partitioning
272 -----------------
273 1. METIS can now directly partition the element node array of finite
274 element meshes. It produces two partitioning vectors. One for the
275 elements and one for the nodes. METIS supports the following
276 elements: triangles, tetrahedra, hexahedra
277
278
279 Mesh-To-Graph Conversion Routines
280 ---------------------------------
281 1. METIS now includes a number of mesh conversion functions that can
282 be used to create the dual and nodal graphs directly from the
283 element connectivity arrays. These are highly optimized routines.
284
285
286