Package elki.math.linearalgebra

Class LinearEquationSystem

  • public class LinearEquationSystem
extends java.lang.Object
    Class for systems of linear equations.
    Since:
    0.1
    Author:
    Elke Achtert

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double[][] coeff
      The matrix of coefficients.
      private int[] col
      Encodes column permutations, column j is at position col[j].
      private static double DELTA
      A small number to handle numbers near 0 as 0.
      private static Logging LOG
      Logger.
      private int rank
      The rank of the coefficient matrix.
      private boolean reducedRowEchelonForm
      Indicates if linear equation system is in reduced row echelon form.
      private double[] rhs
      The right hand side of the equation system.
      private int[] row
      Encodes row permutations, row i is at position row[i].
      private boolean solvable
      Indicates if linear equation system is solvable.
      private boolean solved
      Indicates if solvability has been checked.
      private static int TOTAL_PIVOT_SEARCH
      Indicates total pivot search strategy.
      private static int TRIVAL_PIVOT_SEARCH
      Indicates trivial pivot search strategy.
      private double[][] u
      Holds the space of solutions of the homogeneous linear equation system.
      private double[] x_0
      Holds the special solution vector.

    • Constructor Summary

      Constructors 
      Constructor Description
      LinearEquationSystem​(double[][] a, double[] b)
      Constructs a linear equation system with given coefficient matrix a and right hand side b.
      LinearEquationSystem​(double[][] a, double[] b, int[] rowPermutations, int[] columnPermutations)
      Constructs a linear equation system with given coefficient matrix a and right hand side b.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.lang.String equationsToString​(int fractionDigits)
      Returns a string representation of this equation system.
      java.lang.String equationsToString​(java.lang.String prefix, int fractionDigits)
      Returns a string representation of this equation system.
      java.lang.String equationsToString​(java.lang.String prefix, java.text.NumberFormat nf)
      Returns a string representation of this equation system.
      java.lang.String equationsToString​(java.text.NumberFormat nf)
      Returns a string representation of this equation system.
      private java.lang.StringBuilder format​(java.text.NumberFormat nf, java.lang.StringBuilder buffer, double value, int maxIntegerDigits)
      Helper method for output of equations and solution.
      double[][] getCoefficents()
      Returns a copy of the coefficient array of this linear equation system.
      int[] getColumnPermutations()
      Returns a copy of the column permutations, column i is at position column[i].
      double[] getRHS()
      Returns a copy of the right hand side of this linear equation system.
      int[] getRowPermutations()
      Returns a copy of the row permutations, row i is at position row[i].
      private int integerDigits​(double d)
      Returns the integer digits of the specified double value.
      boolean isSolvable()
      Checks if a solved system is solvable.
      private boolean isSolvable​(int method)
      Checks solvability of this linear equation system with the chosen method.
      boolean isSolved()
      Tests if system has already been tested for solvability.
      private int maxIntegerDigits​(double[] values)
      Returns the maximum integer digits of the specified values.
      private int[] maxIntegerDigits​(double[][] values)
      Returns the maximum integer digits in each column of the specified values.
      private void nonZeroPivotSearch​(int k, int[] pivotpos)
      Method for trivial pivot search, searches for non-zero entry.
      private void permutePivot​(int r1, int c1, int r2, int c2)
      permutes two matrix rows and two matrix columns
      private void pivotOperation​(int k)
      performs a pivot operation
      private void reducedRowEchelonForm​(int method)
      Brings this linear equation system into reduced row echelon form with choice of pivot method.
      java.lang.String solutionToString​(int fractionDigits)
      Returns a string representation of the solution of this equation system.
      private void solve​(int method)
      solves linear system with the chosen method
      void solveByTotalPivotSearch()
      Solves this linear equation system by total pivot search.
      void solveByTrivialPivotSearch()
      Solves this linear equation system by trivial pivot search.
      int subspacedim()
      Return dimensionality of spanned subspace.
      private void totalPivotSearch​(int k, int[] pivotpos)
      Method for total pivot search, searches for x,y in {k,...n}, so that |a_xy| > |a_ij|

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • LOG

        private static final Logging LOG
        Logger.

      • DELTA

        private static final double DELTA
        A small number to handle numbers near 0 as 0.
        See Also:
        Constant Field Values

      • TRIVAL_PIVOT_SEARCH

        private static final int TRIVAL_PIVOT_SEARCH
        Indicates trivial pivot search strategy.
        See Also:
        Constant Field Values

      • TOTAL_PIVOT_SEARCH

        private static final int TOTAL_PIVOT_SEARCH
        Indicates total pivot search strategy.
        See Also:
        Constant Field Values

      • solvable

        private boolean solvable
        Indicates if linear equation system is solvable.

      • solved

        private boolean solved
        Indicates if solvability has been checked.

      • rank

        private int rank
        The rank of the coefficient matrix.

      • coeff

        private double[][] coeff
        The matrix of coefficients.

      • rhs

        private double[] rhs
        The right hand side of the equation system.

      • row

        private int[] row
        Encodes row permutations, row i is at position row[i].

      • col

        private int[] col
        Encodes column permutations, column j is at position col[j].

      • x_0

        private double[] x_0
        Holds the special solution vector.

      • u

        private double[][] u
        Holds the space of solutions of the homogeneous linear equation system.

      • reducedRowEchelonForm

        private boolean reducedRowEchelonForm
        Indicates if linear equation system is in reduced row echelon form.

    • Constructor Detail

      • LinearEquationSystem

        public LinearEquationSystem​(double[][] a,
                            double[] b)
        Constructs a linear equation system with given coefficient matrix a and right hand side b.
        Parameters:
        a - the matrix of the coefficients of the linear equation system
        b - the right hand side of the linear equation system

      • LinearEquationSystem

        public LinearEquationSystem​(double[][] a,
                            double[] b,
                            int[] rowPermutations,
                            int[] columnPermutations)
        Constructs a linear equation system with given coefficient matrix a and right hand side b.
        Parameters:
        a - the matrix of the coefficients of the linear equation system
        b - the right hand side of the linear equation system
        rowPermutations - the row permutations, row i is at position row[i]
        columnPermutations - the column permutations, column i is at position column[i]

    • Method Detail

      • getCoefficents

        public double[][] getCoefficents()
        Returns a copy of the coefficient array of this linear equation system.
        Returns:
        a copy of the coefficient array of this linear equation system

      • getRHS

        public double[] getRHS()
        Returns a copy of the right hand side of this linear equation system.
        Returns:
        a copy of the right hand side of this linear equation system

      • getRowPermutations

        public int[] getRowPermutations()
        Returns a copy of the row permutations, row i is at position row[i].
        Returns:
        a copy of the row permutations

      • getColumnPermutations

        public int[] getColumnPermutations()
        Returns a copy of the column permutations, column i is at position column[i].
        Returns:
        a copy of the column permutations

      • isSolved

        public boolean isSolved()
        Tests if system has already been tested for solvability.
        Returns:
        true if a solution has already been computed, false otherwise.

      • solveByTotalPivotSearch

        public void solveByTotalPivotSearch()
        Solves this linear equation system by total pivot search. "Total pivot search" takes as pivot element the element in the current column having the biggest value. If we have: 
         ( a_11   ...          a_1n      )
 (  0     ...          a_2n      )
 (  0 ... a_ii     ... a_in      )
 (  0 ... a_(i+1)i ... a_(i+1)n  )
 (  0 ... a_ni     ... a_nn      )
        Then we search for x,y in {i,...n}, so that |a_xy| > |a_ij|

      • solveByTrivialPivotSearch

        public void solveByTrivialPivotSearch()
        Solves this linear equation system by trivial pivot search. "Trivial pivot search" takes as pivot element the next element in the current column beeing non zero.

      • isSolvable

        public boolean isSolvable()
        Checks if a solved system is solvable.
        Returns:
        true if this linear equation system is solved and solvable

      • equationsToString

        public java.lang.String equationsToString​(java.lang.String prefix,
                                          int fractionDigits)
        Returns a string representation of this equation system.
        Parameters:
        prefix - the prefix of each line
        fractionDigits - the number of fraction digits for output accuracy
        Returns:
        a string representation of this equation system

      • equationsToString

        public java.lang.String equationsToString​(java.lang.String prefix,
                                          java.text.NumberFormat nf)
        Returns a string representation of this equation system.
        Parameters:
        prefix - the prefix of each line
        nf - the number format
        Returns:
        a string representation of this equation system

      • equationsToString

        public java.lang.String equationsToString​(java.text.NumberFormat nf)
        Returns a string representation of this equation system.
        Parameters:
        nf - the number format
        Returns:
        a string representation of this equation system

      • equationsToString

        public java.lang.String equationsToString​(int fractionDigits)
        Returns a string representation of this equation system.
        Parameters:
        fractionDigits - the number of fraction digits for output accuracy
        Returns:
        a string representation of this equation system

      • solutionToString

        public java.lang.String solutionToString​(int fractionDigits)
        Returns a string representation of the solution of this equation system.
        Parameters:
        fractionDigits - precision
        Returns:
        a string representation of the solution of this equation system

      • reducedRowEchelonForm

        private void reducedRowEchelonForm​(int method)
        Brings this linear equation system into reduced row echelon form with choice of pivot method.
        Parameters:
        method - the pivot search method to use

      • totalPivotSearch

        private void totalPivotSearch​(int k,
                              int[] pivotpos)
        Method for total pivot search, searches for x,y in {k,...n}, so that |a_xy| > |a_ij|
        Parameters:
        k - search starts at entry (k,k)
        pivotpos - Output pivot positions

      • nonZeroPivotSearch

        private void nonZeroPivotSearch​(int k,
                                int[] pivotpos)
        Method for trivial pivot search, searches for non-zero entry.
        Parameters:
        k - search starts at entry (k,k)
        pivotpos - Output array

      • permutePivot

        private void permutePivot​(int r1,
                          int c1,
                          int r2,
                          int c2)
        permutes two matrix rows and two matrix columns
        Parameters:
        r1 - the first row for the permutation
        c1 - the first column for the permutation
        r2 - the second row for the permutation
        c2 - the second column for the permutation

      • pivotOperation

        private void pivotOperation​(int k)
        performs a pivot operation
        Parameters:
        k - pivoting takes place below (k,k)

      • solve

        private void solve​(int method)
            throws java.lang.NullPointerException
        solves linear system with the chosen method
        Parameters:
        method - the pivot search method
        Throws:
        java.lang.NullPointerException

      • isSolvable

        private boolean isSolvable​(int method)
                    throws java.lang.NullPointerException
        Checks solvability of this linear equation system with the chosen method.
        Parameters:
        method - the pivot search method
        Returns:
        true if linear system in solvable
        Throws:
        java.lang.NullPointerException

      • maxIntegerDigits

        private int[] maxIntegerDigits​(double[][] values)
        Returns the maximum integer digits in each column of the specified values.
        Parameters:
        values - the values array
        Returns:
        the maximum integer digits in each column of the specified values

      • maxIntegerDigits

        private int maxIntegerDigits​(double[] values)
        Returns the maximum integer digits of the specified values.
        Parameters:
        values - the values array
        Returns:
        the maximum integer digits of the specified values

      • integerDigits

        private int integerDigits​(double d)
        Returns the integer digits of the specified double value.
        Parameters:
        d - the double value
        Returns:
        the integer digits of the specified double value

      • format

        private java.lang.StringBuilder format​(java.text.NumberFormat nf,
                                       java.lang.StringBuilder buffer,
                                       double value,
                                       int maxIntegerDigits)
        Helper method for output of equations and solution. Appends the specified double value to the given string buffer according the number format and the maximum number of integer digits.
        Parameters:
        nf - the number format
        buffer - the string buffer to append the value to
        value - the value to append
        maxIntegerDigits - the maximum number of integer digits
        Returns:
        the buffer for chaining

      • subspacedim

        public int subspacedim()
        Return dimensionality of spanned subspace.
        Returns:
        dim