| 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 |
|