Package edu.udel.cis.vsl.sarl.simplify.simplifier

Class LinearSolver

java.lang.Object
edu.udel.cis.vsl.sarl.simplify.simplifier.LinearSolver
public class LinearSolver extends Object

A class used to simplify a constant map by applying linear reasoning. The numeric (integer and real) entries in the constant map are separated and used to form coefficient matrices, where the "variables" are Monics. These matrices are placed in reduced row echelon form using Gaussian elimination. The new entries for the substitution map are obtained by translating each row of these matrices back to a substitution. The client may choose to use backwards substitution or not.

The easiest way to use this class is through the two static methods reduce(SimplifierUtility, Map, Comparator, boolean) and reduceRelative(SimplifierUtility, Map, Map, Comparator, boolean).

If an inconsistency exists (for example, X+Y maps to 0, X maps to 0, Y maps to 1) in the map, this will be discovered in the elimination. The method isConsistent() can be used to determine if an inconsistency has been detected. Another method hasChanged() can tell if any changes resulted from the process.

This class will not modify the original substitution map. Rather, it provides two methods which specify the changes that must be made to the original substitution map in order to bring it into sync with this solver. This is for efficiency reasons, and also because it is best to let the client modify her substitution map, since she may want to apply complicated normalized forms before adding new entries, and those transformations are not available to this solver.

  • Method Details

    • hasChanged

      public boolean hasChanged()
      Will the new map result in any change to the original substitution map? If not, nothing more need be done.
      Returns:
      true if some change must happen to the substitution map, else false

    • isConsistent

      public boolean isConsistent()
      Is the linear system consistent?
      Returns:
      false if the linear system has been determined to be inconsistent, else true

    • reduce

      public void reduce()
      Performs Gaussian elimination on the intMatrix and realMatrix to place those matrices into reduced row echelon form.

    • reduceRelativeTo

      public void reduceRelativeTo(LinearSolver context)
      Performs a Gaussian elimination "relative to" a fixed context.
      Parameters:
      context -

    • getKeysToRemove

      public Collection<SymbolicExpression> getKeysToRemove()
      Returns the set of keys in the original map which should be removed as the first step to bring that map in sync with the state of this solver.
      Returns:
      a set of symbolic expressions, each of which occurs as a key in originalMap; these keys should be removed from the map by the client

    • getNewEntries

      public Collection<Map.Entry<Monic,Monomial>> getNewEntries()
      Returns the set of entries which should be entered into the original map in order to bring it in sync with the state of this solver. The client should perform that modification after removing the keys that need to be removed.
      Returns:
      the set of new entries that must be applied to the original map

    • reduce

      public static LinearSolver reduce(SimplifierUtility info, Map<SymbolicExpression,SymbolicExpression> map, Comparator<Monic> monicComparator, boolean backwardsSub)

    • reduceRelative

      public static LinearSolver reduceRelative(SimplifierUtility info, Map<SymbolicExpression,SymbolicExpression> context, Map<SymbolicExpression,SymbolicExpression> map, Comparator<Monic> monicComparator, boolean backwardsSub)