edu.stanford.math.plex4.homology.zigzag

Class BasisTrackingUtility

java.lang.Object

edu.stanford.math.plex4.homology.zigzag.BasisTrackingUtility

public class BasisTrackingUtility
extends java.lang.Object

This class contains various static functions for assisting with zigzag homology computations.

Author:

Andrew Tausz

Constructor Summary

Constructors

Constructor and Description
BasisTrackingUtility()

Method Summary

Methods

Modifier and Type	Method and Description
static <X> int	appendColumn(java.util.Map<java.lang.Integer,X> m, X col)
static <X extends PrimitiveBasisElement> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>	computeBoundary(edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> chain, edu.stanford.math.primitivelib.autogen.formal_sum.IntAlgebraicFreeModule<X> chainModule) This function computes the boundary of a given chain, by linear extension.
static <X extends PrimitiveBasisElement> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>	createNewSum(int[] coefficients, PrimitiveBasisElement[] objects) This function creates a new formal sum from the given set of coefficients and objects.
static <Y> int	findColumnWithGivenLow(java.util.List<edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y low, java.util.Comparator<Y> comparator) This function finds the index of the first column such that the column's low value is the value specified.
static <X,Y> X	findColumnWithGivenLow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y low, java.util.Comparator<Y> comparator) This function finds the index of the first column such that the column's low value is the value specified.
static <X,Y> X	findFirstIndexContainingElement(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y element, java.util.Comparator<X> comparator) This function returns the lowest index such that the given element is found in the chain at that index.
static <X,Y> X	findLastIndexContainingElement(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y element, java.util.Comparator<X> comparator) This function returns the greatest index such that the given element is found in the chain at that index.
static <X> int	getAppendIndex(java.util.Map<java.lang.Integer,X> m)
static <X,Y> java.util.List<X>	getAscendingIndices(java.util.Map<X,Y> m, java.util.Comparator<X> comparator)
static <X,Y> java.util.List<X>	getAscendingIndicesContainingElement(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y element, java.util.Comparator<X> comparator) This function returns the set of indices such that the chains at the indices contain the given element.
static <X,Y> java.util.List<X>	getAscendingIndicesWithGivenLow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y element, java.util.Comparator<X> comparator, java.util.Comparator<Y> comparatorY)
static <X> int	getPrependIndex(java.util.Map<java.lang.Integer,X> m)
static <X,Y> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>	getRow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, Y row)
static <X> X	low(edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> chain, java.util.Comparator<X> comparator) This function computes the operation low_A(j) as described in the paper.
static <X,Y> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>	multiply(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m, edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> v, edu.stanford.math.primitivelib.autogen.algebraic.IntAbstractField field) This function performs matrix multiplication.
static <X,Y,Z> java.util.Map<Z,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>>	multiply(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> a, java.util.Map<Z,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>> b, edu.stanford.math.primitivelib.autogen.algebraic.IntAbstractField field) This function performs matrix-matrix multiplication.
static <X> int	prependColumn(java.util.Map<java.lang.Integer,X> m, X col)
static <X,Y> edu.stanford.math.primitivelib.autogen.pair.ObjectObjectPair<edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>>	reduce(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> M, edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y> column, java.util.Comparator<Y> comparator, edu.stanford.math.primitivelib.autogen.formal_sum.IntAlgebraicFreeModule<Y> chainModule)
static <X> void	writeRow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<java.lang.Integer>> m, edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> row, int rowIndex)

Methods inherited from class java.lang.Object

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

Constructor Detail

BasisTrackingUtility

public BasisTrackingUtility()

Method Detail

createNewSum

public static <X extends PrimitiveBasisElement> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> createNewSum(int[] coefficients,
                                                                                                                     PrimitiveBasisElement[] objects)

This function creates a new formal sum from the given set of coefficients and objects.

Type Parameters:

X -

Parameters:

coefficients - the array of coefficients

objects - the array of basis elements - they must be of type X

Returns:

a formal sum containing the given coefficients and basis elements

low

public static <X> X low(edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> chain,
        java.util.Comparator<X> comparator)

This function computes the operation low_A(j) as described in the paper. Note that if the chain is empty (for example the column contains only zeros), then this function returns null.

Type Parameters:

X - the underlying type of the basis elements in the chain

Parameters:

chain - the chain

comparator - the comparator to use

Returns:

the lowest element in the chain

multiply

public static <X,Y> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y> multiply(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                                                                                     edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> v,
                                                                                     edu.stanford.math.primitivelib.autogen.algebraic.IntAbstractField field)

This function performs matrix multiplication. The matrix is represented by a sparse set of sparse columns. In other words, this function computes the linear combination of the columns in the specified map with coefficients given by the vector v. In the matrix m, the keys represent the column labels, and the values are the columns at that particular index.

Type Parameters:

X -

Y -

Parameters:

m - the matrix as a list of columns

v - the vector

field - the field over which to perform the computations

Returns:

the matrix vector product

multiply

public static <X,Y,Z> java.util.Map<Z,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> multiply(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> a,
                                                                                                        java.util.Map<Z,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>> b,
                                                                                                        edu.stanford.math.primitivelib.autogen.algebraic.IntAbstractField field)

This function performs matrix-matrix multiplication. The matrices are represented by a sparse set of sparse columns.

Type Parameters:

X -

Y -

Z -

Parameters:

a - the first matrix

b - the second matrix

field - the field over which to perform the computations

Returns:

the matrix-matrix product a*b

findColumnWithGivenLow

public static <Y> int findColumnWithGivenLow(java.util.List<edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                             Y low,
                             java.util.Comparator<Y> comparator)

This function finds the index of the first column such that the column's low value is the value specified. If no such column exists, it returns -1.

Type Parameters:

Y -

Parameters:

m - the set of columns to search

low - the low value to search for

comparator - the comparator which performs the comparison within type Y

Returns:

the index of the first column with the given low, and -1 if no such column exists

findColumnWithGivenLow

public static <X,Y> X findColumnWithGivenLow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                             Y low,
                             java.util.Comparator<Y> comparator)

This function finds the index of the first column such that the column's low value is the value specified. If no such column exists, it returns null.

Type Parameters:

X -

Y -

Parameters:

m - the set of columns to search

low - the low value to search for

comparator - the comparator which performs the comparison within type Y

Returns:

the index of the first column with the given low, and null if no such column exists

computeBoundary

public static <X extends PrimitiveBasisElement> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> computeBoundary(edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> chain,
                                                                                                                        edu.stanford.math.primitivelib.autogen.formal_sum.IntAlgebraicFreeModule<X> chainModule)

This function computes the boundary of a given chain, by linear extension.

Type Parameters:

X -

Parameters:

chain - the chain to compute the boundary of

chainModule - the module that performs the computations

Returns:

the boundary of the given chain

findFirstIndexContainingElement

public static <X,Y> X findFirstIndexContainingElement(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                                      Y element,
                                      java.util.Comparator<X> comparator)

This function returns the lowest index such that the given element is found in the chain at that index. If no such index is found, it returns null.

Type Parameters:

X -

Y -

Parameters:

m - the set of chains

element - the element to search for

comparator - provides comparison for the indices of m

Returns:

the lowest index of the chains containing the given element

findLastIndexContainingElement

public static <X,Y> X findLastIndexContainingElement(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                                     Y element,
                                     java.util.Comparator<X> comparator)

This function returns the greatest index such that the given element is found in the chain at that index. If no such index is found, it returns null.

Type Parameters:

X -

Y -

Parameters:

m - the set of chains

element - the element to search for

comparator - provides comparison for the indices of m

Returns:

the greatest index of the chains containing the given element

getAscendingIndicesContainingElement

public static <X,Y> java.util.List<X> getAscendingIndicesContainingElement(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                                                           Y element,
                                                           java.util.Comparator<X> comparator)

This function returns the set of indices such that the chains at the indices contain the given element. The indices are returned in sorted order. In the event that no indices are found, it returns the empty list.

Type Parameters:

X -

Y -

Parameters:

m - the set of chains

element - the element to search for

comparator - provides comparison for the indices of m

Returns:

the ascending set of indices containing the element

getAscendingIndicesWithGivenLow

public static <X,Y> java.util.List<X> getAscendingIndicesWithGivenLow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                                                      Y element,
                                                      java.util.Comparator<X> comparator,
                                                      java.util.Comparator<Y> comparatorY)

getAscendingIndices

public static <X,Y> java.util.List<X> getAscendingIndices(java.util.Map<X,Y> m,
                                          java.util.Comparator<X> comparator)

getPrependIndex

public static <X> int getPrependIndex(java.util.Map<java.lang.Integer,X> m)

getAppendIndex

public static <X> int getAppendIndex(java.util.Map<java.lang.Integer,X> m)

prependColumn

public static <X> int prependColumn(java.util.Map<java.lang.Integer,X> m,
                    X col)

appendColumn

public static <X> int appendColumn(java.util.Map<java.lang.Integer,X> m,
                   X col)

writeRow

public static <X> void writeRow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<java.lang.Integer>> m,
                edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> row,
                int rowIndex)

getRow

public static <X,Y> edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X> getRow(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> m,
                                                                                   Y row)

reduce

public static <X,Y> edu.stanford.math.primitivelib.autogen.pair.ObjectObjectPair<edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<X>,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> reduce(java.util.Map<X,edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y>> M,
                                                                                                                                                                                                                         edu.stanford.math.primitivelib.autogen.formal_sum.IntSparseFormalSum<Y> column,
                                                                                                                                                                                                                         java.util.Comparator<Y> comparator,
                                                                                                                                                                                                                         edu.stanford.math.primitivelib.autogen.formal_sum.IntAlgebraicFreeModule<Y> chainModule)