Class MinimumDegree

java.lang.Object
org.ojalgo.matrix.decomposition.MinimumDegree
public final class MinimumDegree extends Object
Approximate Minimum Degree (AMD) style ordering for pre-ordering a symmetric sparse matrix prior to numerical factorisation (Cholesky or LDL). This is NOT the full/correct AMD-algorithm as described by Amestoy, Davis, and Duff, but rather something simpler that aims to accomplish similar results. It is clearly not as fast as a highly tuned proper AMD implementation, but compared to not doing any ordering at all it is found to provide up to 90% of the potential speedup in overall use cases.

This implementation:

  • Assumes the input R064CSC represents a symmetric pattern with only the upper triangle stored.
  • Treats the matrix as an adjacency graph and computes a fill-reducing column ordering.
  • Does not modify the input matrix; it only returns a permutation vector.

  • Field Details

    • myPermutation

      private final Pivot myPermutation

  • Constructor Details

    • MinimumDegree

      public MinimumDegree()

  • Method Details

    • approximate

      public void approximate(R064CSC matrix)
      Approximates a minimum degree ordering for a symmetric R064CSC matrix. The result is stored internally. To permute vectors or matrices according to the computed ordering, use the permute(double[], double[]) or permute(R064CSC, int[])} methods.

      The input is assumed to store only the upper/right triangle of the symmetric pattern; lower-triangular entries (if present) are ignored.

    • permute

      public void permute(double[] destination, double[] source)
      Permutes a vector according to the computed ordering. Copies from source to destination, reordering as it goes.

    • permute

      public R064CSC permute(R064CSC original, int[] recording)
      Permutes a symmetric R064CSC matrix according to the computed ordering. The input is assumed to store only the upper/right triangle of the symmetric pattern.

      Does not modify the input matrix; it returns a new permuted matrix.

    • reverse

      public void reverse(double[] destination, double[] source)
      The inverse permutation of a vector according to the computed ordering. Copies from source to destination, reordering as it goes.

    • getOrder

      int[] getOrder()

    • reverseOrder

      int[] reverseOrder()