Module ojalgo
Package org.ojalgo.matrix.decomposition

Class MinimumDegree

  • public final class MinimumDegree
extends java.lang.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.

    • Constructor Summary

      Constructors 
      Constructor Description
      MinimumDegree()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void approximate​(R064CSC matrix)
      Approximates a minimum degree ordering for a symmetric R064CSC matrix.
      (package private) int[] getOrder()  
      void permute​(double[] destination, double[] source)
      Permutes a vector according to the computed ordering.
      R064CSC permute​(R064CSC original, int[] recording)
      Permutes a symmetric R064CSC matrix according to the computed ordering.
      void reverse​(double[] destination, double[] source)
      The inverse permutation of a vector according to the computed ordering.
      (package private) int[] reverseOrder()  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • myPermutation

        private final Pivot myPermutation

    • Constructor Detail

      • MinimumDegree

        public MinimumDegree()

    • Method Detail

      • 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()