ginkgo icon indicating copy to clipboard operation
ginkgo copied to clipboard

Published 20 hours ago • verified publisher icon ginkgo-project

Add MC64

Open fritzgoebel opened this issue 2 years ago • 4 comments

This PR adds the MC64 reordering and equilibration algorithm.

MC64 moves large matrix entries to the diagonal, this implementation supports two strategies: maximizing the sum or the product of the absolute values of the diagonal entries. Depending on the strategy, the weights for the bipartite graph used in the algorithm are computed in a different way.

MC64 computes a minimum weight perfect matching on a weighted edge bipartite graph. This is done in two steps:

  • Find an initial matching with a simple procedure
  • For each unmatched row not part of the initial matching, a shortest augmenting path is computed with a variant of Dijkstra's algorithm. This increases the matching size by 1.

If the goal is to maximize the product of the diagonal entries, scaling coefficients are generated that guarantee absolute values of one on the diagonal and smaller or equal than that everywhere else.

For a detailed description of the algorithm see the paper On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix by Duff and Koster.

Note: most of the added lines are test matrices.

fritzgoebel avatar Sep 15 '22 15:09 fritzgoebel

format!

fritzgoebel avatar Sep 15 '22 16:09 fritzgoebel

Error: Cannot push formatted branch, are edits for maintainers allowed?

ginkgo-bot avatar Sep 15 '22 16:09 ginkgo-bot

format!

fritzgoebel avatar Sep 16 '22 07:09 fritzgoebel

Note: This PR changes the Ginkgo ABI:

Functions changes summary: 0 Removed, 0 Changed, 1317 Added functions
Variables changes summary: 0 Removed, 0 Changed, 0 Added variable

For details check the full ABI diff under Artifacts here

ginkgo-bot avatar Sep 16 '22 09:09 ginkgo-bot

format!

upsj avatar Nov 03 '23 00:11 upsj

SonarCloud Quality Gate failed.    Quality Gate failed

Bug C 3 Bugs
Vulnerability A 0 Vulnerabilities
Security Hotspot A 0 Security Hotspots
Code Smell A 30 Code Smells

98.0% 98.0% Coverage
0.0% 0.0% Duplication

warning The version of Java (11.0.3) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17. Read more here

idea Catch issues before they fail your Quality Gate with our IDE extension sonarlint SonarLint

sonarqubecloud[bot] avatar Nov 06 '23 22:11 sonarqubecloud[bot]