edu.umbc.cs.maple.utils
Class MathUtils

java.lang.Object
  edu.umbc.cs.maple.utils.MathUtils

public class MathUtils
extends java.lang.Object

A collection of mathematical utility functions.

Copyright (c) 2008 Eric Eaton

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Version:

0.1

Author:

Eric Eaton (EricEaton@umbc.edu)
University of Maryland Baltimore County

Nested Class Summary

static class

MathUtils.SimilarityMetric Defines a similarity metric measure

Constructor Summary

MathUtils()

Method Summary

static double[]	append(double[] v1, double d) Appends an element to a vector.
static double[]	append(double[] v1, double[] v2) Appends two vectors.
static int[]	append(int[] v1, int d) Appends an element to a vector.
static int[]	append(int[] v1, int[] v2) Appends two vectors.
static double[]	arrayAdd(double[] d1, double[] d2) Adds corresponding elements of two arrays.
static double[]	arrayDivide(double[] d1, double denominator) Divides each element of an array by a number.
static double	capValue(double value, double minValue, double maxValue) Caps a value to a given range.
static int	capValue(int value, int minValue, int maxValue) Caps a value to a given range.
static double	computeSimilarity(int[] targetV, int[] v, MathUtils.SimilarityMetric similarityMetric) Computes the similarity of the two vectors.
static double	correlation(double[] p, double[] q) Computes the correlation between two arrays of the same length, p and q.
static double	correlation(int[] p, int[] q) Computes the correlation between two arrays of the same length, p and q.
static double[][]	getConfusionMatrix(int[] p, int[] q) Computes the normalized confusion matrix for two vectors.
static double	getMachinePrecision() Gets the computed machine precision.
static java.util.Random	getRandomGenerator() Retrieves the initialized random number generator.
static void	initializeRandomGenerator(long seed) Initializes a random number generator with the given seed.
static boolean	isApproxEqual(double value1, double value2) Determines whether two numbers are approximately equal according to the machine precision.
static boolean	isApproxEqual(double value1, double value2, double precision) Determines whether two numbers are approximately equal according to the precision.
static double	log2(double d) Computes the log-base-2 of a number.
static void	main(java.lang.String[] args)
static int	maxIndex(double[] v) Gets the index of the maximum element in the array.
static int	maxIndex(int[] v) Gets the index of the maximum element in the array.
static int	maxIndexRand(double[] v) Gets the index of the maximum element in the array.
static int	maxIndexRand(int[] v) Gets the index of the maximum element in the array.
static double	maxValue(double[] values) Computes the maximum value in the given array.
static int	maxValue(int[] values) Computes the maximum value in the given array.
static double	mean(double[] values) Computes the mean of the values in the given array.
static double	mean(int[] values) Computes the mean of the values in the given array.
static int	minIndex(double[] v) Gets the index of the minimum element in the array.
static int	minIndex(int[] v) Gets the index of the minimum element in the array.
static int	minIndexRand(double[] v) Gets the index of the minimum element in the array.
static int	minIndexRand(int[] v) Gets the index of the minimum element in the array.
static double	minValue(double[] values) Computes the minimum value in the given array.
static int	minValue(int[] values) Computes the minimum value in the given array.
static double	mutualInformation(int[] p, int[] q) Computes the mutual information between two vectors.
static double	nextRandomGaussian(double mean, double stdev) Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.
static double	nextRandomGaussian(java.util.Random randGenerator, double mean, double stdev) Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.
static double	pairwiseAgreement(int[] p, int[] q) Computes the pairwise agreement between two pairwise arrays of labelings.
static int[]	permutation(int n) Generates a random permutation of the numbers {0, ..., n-1}
static int[]	permutation(int n, java.util.Random rand) Generates a random permutation of the numbers {0, ..., n-1}
static void	rangeCheck(double value, double min, double max) Throws an exception whenever a value falls outside the given range.
static void	rangeCheck(int value, int min, int max) Throws an exception whenever a value falls outside the given range.
static double[]	reverse(double[] array) Reverses the given array.
static int[]	reverse(int[] array) Reverses the given array.
static int[]	reverseCuthillMcKee(int[][] adjacencyLists, boolean runTwiceForOptimalResult) Runs the reverse Cuthill-McKee algorithm on the adjacency lists to provide an efficient ordering of the vertices
static double	rmse(double[] a, double[] b) Computes the root mean squared error between two vectors.
static double	round(double d, int decimalPlacesRequired) Reduces the precision of a double to a specified number of decimal places.
static int	roundToMultiple(int value, int multipleOf) Rounds a value to the nearest number that is a specific multiple.
static <T> java.util.Collection<T>	sampleWithoutReplacement(T[] objs, double[] probabilityDistribution, int numSamples) Samples from a set of weighted objects without replacement.
static <T> java.util.Collection<T>	sampleWithReplacement(T[] objs, double[] probabilityDistribution, int numSamples) Samples from a set of weighted objects with replacement.
static int[]	sortOrder(double[] values) Sorts the given values and returns the order of the original indices.
static int[]	sortOrder(int[] values) Sorts the given values and returns the order of the original indices.
static double	sum(double[] values) Sums the values in the given array.
static int	sum(int[] values) Sums the values in the given array.
static double[]	uniqueValues(double[] v) Determines the unique values of v.
static int[]	uniqueValues(int[] v) Determines the unique values of v.
static double[]	vectorAdd(double[] v1, double[] v2) Performs vector addition.
static double	vectorL2Norm(double[] v) Computes the L2 norm of the given vector.
static double[]	vectorMultiply(double s, double[] v) Performs scalar multiplication on a vector.
static double[]	vectorNormalize(double[] v) Normalizes the given vector.
static double[]	vectorSubtract(double[] v1, double[] v2) Performs vector subtraction.

Methods inherited from class java.lang.Object

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

Constructor Detail

MathUtils

public MathUtils()

Method Detail

reverseCuthillMcKee

public static int[] reverseCuthillMcKee(int[][] adjacencyLists,
                                        boolean runTwiceForOptimalResult)

Runs the reverse Cuthill-McKee algorithm on the adjacency lists to provide an efficient ordering of the vertices

Parameters:

adjacencyLists - a list of the adjacency lists of the graph

runTwiceForOptimalResult - whether to run the algorithm twice to get the optimal result

Returns:

a permutation of the vertices that is efficient for a sparse matrix

permutation

public static int[] permutation(int n)

Generates a random permutation of the numbers {0, ..., n-1}

Parameters:

n - the length of the set of numbers to permute

Returns:

a random permutation of the numbers {0, ..., n-1}

permutation

public static int[] permutation(int n,
                                java.util.Random rand)

Generates a random permutation of the numbers {0, ..., n-1}

Parameters:

n - the length of the set of numbers to permute

rand - the random number generator

Returns:

a random permutation of the numbers {0, ..., n-1}

append

public static int[] append(int[] v1,
                           int d)

Appends an element to a vector.

Parameters:

v1 - the vector.

d - the element to append.

Returns:

A vector containing all the elements of v1 followed by d.

append

public static double[] append(double[] v1,
                              double d)

Appends an element to a vector.

Parameters:

v1 - the vector.

d - the element to append.

Returns:

A vector containing all the elements of v1 followed by d.

append

public static double[] append(double[] v1,
                              double[] v2)

Appends two vectors.

Parameters:

v1 - the first vector.

v2 - the second vector.

Returns:

A vector containing all the elements of v1 followed by all the elements of v2.

append

public static int[] append(int[] v1,
                           int[] v2)

Appends two vectors.

Parameters:

v1 - the first vector.

v2 - the second vector.

Returns:

A vector containing all the elements of v1 followed by all the elements of v2.

vectorAdd

public static double[] vectorAdd(double[] v1,
                                 double[] v2)

Performs vector addition.

Parameters:

v1 - the first vector.

v2 - the second vector.

Returns:

v1 + v2

vectorSubtract

public static double[] vectorSubtract(double[] v1,
                                      double[] v2)

Performs vector subtraction.

Parameters:

v1 - the first vector.

v2 - the second vector.

Returns:

v1 - v2

vectorMultiply

public static double[] vectorMultiply(double s,
                                      double[] v)

Performs scalar multiplication on a vector.

Parameters:

s - a scalar value.

v - the vector.

Returns:

the scalar product of s and v.

vectorL2Norm

public static double vectorL2Norm(double[] v)

Computes the L2 norm of the given vector.

Parameters:

v - the vector.

Returns:

the L2 norm of v.

vectorNormalize

public static double[] vectorNormalize(double[] v)

Normalizes the given vector.

Parameters:

v - the vector.

Returns:

v with the values normalized.

getRandomGenerator

public static java.util.Random getRandomGenerator()

Retrieves the initialized random number generator. Use of this rand generator allows an entire program to use a single rand generator.

Returns:

the initialized random number generator.

initializeRandomGenerator

public static void initializeRandomGenerator(long seed)

Initializes a random number generator with the given seed. Repeated calls to this initialize function create a new random generator.

Parameters:

seed - the seed for the random generator.

nextRandomGaussian

public static double nextRandomGaussian(double mean,
                                        double stdev)

Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.

Parameters:

mean - the mean of the Gaussian

stdev - the standard deviation of the Gaussian

Returns:

a random number from the specified distribution

nextRandomGaussian

public static double nextRandomGaussian(java.util.Random randGenerator,
                                        double mean,
                                        double stdev)

Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.

Parameters:

randGenerator - the random generator.

mean - the mean of the Gaussian

stdev - the standard deviation of the Gaussian

Returns:

a random number from the specified distribution

rmse

public static double rmse(double[] a,
                          double[] b)

Computes the root mean squared error between two vectors.

Parameters:

a -

b -

Returns:

the RMSE between a and b

main

public static void main(java.lang.String[] args)

sampleWithoutReplacement

public static <T> java.util.Collection<T> sampleWithoutReplacement(T[] objs,
                                                                   double[] probabilityDistribution,
                                                                   int numSamples)

Samples from a set of weighted objects without replacement.

Parameters:

objs - the array of objects

probabilityDistribution - the probability distribution over the set of objects (i.e. the weight assigned to each object)

numSamples - the desired number of samples

sampleWithReplacement

public static <T> java.util.Collection<T> sampleWithReplacement(T[] objs,
                                                                double[] probabilityDistribution,
                                                                int numSamples)

Samples from a set of weighted objects with replacement.

Parameters:

objs - the array of objects

probabilityDistribution - the probability distribution over the set of objects (i.e. the weight assigned to each object)

numSamples - the desired number of samples

capValue

public static double capValue(double value,
                              double minValue,
                              double maxValue)

Caps a value to a given range.

Parameters:

value - the value to constrain.

minValue - the min value.

maxValue - the max value.

Returns:

the value altered to lie in [minValue, maxValue].

capValue

public static int capValue(int value,
                           int minValue,
                           int maxValue)

Caps a value to a given range.

Parameters:

value - the value to constrain.

minValue - the min value.

maxValue - the max value.

Returns:

the value altered to lie in [minValue, maxValue].

rangeCheck

public static void rangeCheck(int value,
                              int min,
                              int max)

Throws an exception whenever a value falls outside the given range.

Parameters:

value -

min - the minimal value

max - the maximal value

Throws:

java.lang.IllegalArgumentException - if the value is outside of the given range.

rangeCheck

public static void rangeCheck(double value,
                              double min,
                              double max)

Throws an exception whenever a value falls outside the given range.

Parameters:

value -

min - the minimal value

max - the maximal value

Throws:

java.lang.IllegalArgumentException - if the value is outside of the given range.

round

public static final double round(double d,
                                 int decimalPlacesRequired)

Reduces the precision of a double to a specified number of decimal places.

Parameters:

d - number to reduce precision

decimalPlacesRequired - the number of required decimal places

Returns:

d reduced to the specified precision

roundToMultiple

public static final int roundToMultiple(int value,
                                        int multipleOf)

Rounds a value to the nearest number that is a specific multiple.

Parameters:

value - the value to round

multipleOf - the value that the final number should be a multiple of.

Returns:

value rounded to the nearest number that is a multiple of multipleOf.

minIndex

public static int minIndex(double[] v)

Gets the index of the minimum element in the array. Returns the first min index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the minimum element of v.

minIndex

public static int minIndex(int[] v)

Gets the index of the minimum element in the array. Returns the first min index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the minimum element of v.

minIndexRand

public static int minIndexRand(double[] v)

Gets the index of the minimum element in the array. Randomly chooses the min index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the minimum element of v.

minIndexRand

public static int minIndexRand(int[] v)

Gets the index of the minimum element in the array. Randomly chooses the min index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the minimum element of v.

maxIndex

public static int maxIndex(double[] v)

Gets the index of the maximum element in the array. Returns the first max index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the maximum element of v.

maxIndex

public static int maxIndex(int[] v)

Gets the index of the maximum element in the array. Returns the first max index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the maximum element of v.

maxIndexRand

public static int maxIndexRand(double[] v)

Gets the index of the maximum element in the array. Randomly chooses the max index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the maximum element of v.

maxIndexRand

public static int maxIndexRand(int[] v)

Gets the index of the maximum element in the array. Randomly chooses the max index if there are multiple matching elements.

Parameters:

v -

Returns:

the index of the maximum element of v.

maxValue

public static int maxValue(int[] values)

Computes the maximum value in the given array.

Parameters:

values -

Returns:

the maximum value in the given array.

maxValue

public static double maxValue(double[] values)

Computes the maximum value in the given array.

Parameters:

values -

Returns:

the maximum value in the given array.

minValue

public static double minValue(double[] values)

Computes the minimum value in the given array.

Parameters:

values -

Returns:

the minimum value in the given array.

minValue

public static int minValue(int[] values)

Computes the minimum value in the given array.

Parameters:

values -

Returns:

the minimum value in the given array.

mean

public static double mean(double[] values)

Computes the mean of the values in the given array.

Parameters:

values -

Returns:

the mean of the values in the given array.

mean

public static double mean(int[] values)

Computes the mean of the values in the given array.

Parameters:

values -

Returns:

the mean of the values in the given array.

sum

public static double sum(double[] values)

Sums the values in the given array.

Parameters:

values -

Returns:

the sum of the values in the given array.

sum

public static int sum(int[] values)

Sums the values in the given array.

Parameters:

values -

Returns:

the sum of the values in the given array.

arrayAdd

public static double[] arrayAdd(double[] d1,
                                double[] d2)

Adds corresponding elements of two arrays.

Parameters:

d1 - the first array

d2 - the second array

Returns:

the element-wise sum of d1 + d2

arrayDivide

public static double[] arrayDivide(double[] d1,
                                   double denominator)

Divides each element of an array by a number.

Parameters:

d1 - the first array

denominator - the denominator for the devision

Returns:

d1 / denominator

sortOrder

public static int[] sortOrder(int[] values)

Sorts the given values and returns the order of the original indices.

Parameters:

values - the values to sort

Returns:

an array of the original indices of values reordered according to the sort.

sortOrder

public static int[] sortOrder(double[] values)

Sorts the given values and returns the order of the original indices.

Parameters:

values - the values to sort

Returns:

an array of the original indices of values reordered according to the sort.

reverse

public static int[] reverse(int[] array)

Reverses the given array.

Parameters:

array -

Returns:

the array with the elements in reverse order

reverse

public static double[] reverse(double[] array)

Reverses the given array.

Parameters:

array -

Returns:

the array with the elements in reverse order

getMachinePrecision

public static double getMachinePrecision()

Gets the computed machine precision.

Returns:

the computed machine precision.

isApproxEqual

public static boolean isApproxEqual(double value1,
                                    double value2)

Determines whether two numbers are approximately equal according to the machine precision.

Parameters:

value1 -

value2 -

Returns:

whether the two numbers are approximately equal

isApproxEqual

public static boolean isApproxEqual(double value1,
                                    double value2,
                                    double precision)

Determines whether two numbers are approximately equal according to the precision.

Parameters:

value1 -

value2 -

precision -

Returns:

whether the two numbers are approximately equal

correlation

public static double correlation(int[] p,
                                 int[] q)

Computes the correlation between two arrays of the same length, p and q. Computes the correlation between p and q as r = (|p| * \sum_i(p[i]*q[i]) - \sum_i(p[i]) * \sum_i(q[i]))/ sqrt((|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2) * (|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2)) This correlation can be tested for statistical significance via t-tests. See e.g.: http://www.socialresearchmethods.net/kb/statcorr.htm

Returns:

The correlation between the elements of the two arrays.

correlation

public static double correlation(double[] p,
                                 double[] q)

Computes the correlation between two arrays of the same length, p and q. Computes the correlation between p and q as r = (|p| * \sum_i(p[i]*q[i]) - \sum_i(p[i]) * \sum_i(q[i]))/ sqrt((|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2) * (|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2)) This correlation can be tested for statistical significance via t-tests. See e.g.: http://www.socialresearchmethods.net/kb/statcorr.htm

Returns:

The correlation between the elements of the two arrays.

pairwiseAgreement

public static double pairwiseAgreement(int[] p,
                                       int[] q)

Computes the pairwise agreement between two pairwise arrays of labelings. The pairwise agreement is the number-of-pairs-in-agreement / the-total-number-of-pairs. The two arrays must be the same length.

Parameters:

p - An array of labels.

q - An array of labels.

Returns:

The pairwise agreement between the labelings in p and q.

uniqueValues

public static int[] uniqueValues(int[] v)

Determines the unique values of v. The values are returned in no particular order.

Parameters:

v -

Returns:

the unique values of v in no particular order.

uniqueValues

public static double[] uniqueValues(double[] v)

Determines the unique values of v. The values are returned in no particular order.

Parameters:

v -

Returns:

the unique values of v in no particular order.

getConfusionMatrix

public static double[][] getConfusionMatrix(int[] p,
                                            int[] q)

Computes the normalized confusion matrix for two vectors.

Parameters:

p - the first vector

q - the second vector

Returns:

the normalized confusion matrix for p and q

mutualInformation

public static double mutualInformation(int[] p,
                                       int[] q)

Computes the mutual information between two vectors.

Parameters:

p - the first vector.

q - the second vector.

Returns:

the mutual information between p and q.

computeSimilarity

public static double computeSimilarity(int[] targetV,
                                       int[] v,
                                       MathUtils.SimilarityMetric similarityMetric)

Computes the similarity of the two vectors.

Parameters:

targetV - the target vector that forms the basis for comparison.

v - the vector for comparison

similarityMetric - the metric to use for computing the similarity

Returns:

The similarity of the two models.

log2

public static double log2(double d)

Computes the log-base-2 of a number.

Parameters:

d -

Returns:

the log-base-2 of d