http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/IdentityValueMapper.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/IdentityValueMapper.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/IdentityValueMapper.java new file mode 100644 index 0000000..00bf915 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/IdentityValueMapper.java @@ -0,0 +1,53 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +/** + * Identity value mapper. + */ +public class IdentityValueMapper implements ValueMapper<Double> { + /** */ private static final long serialVersionUID = -8010078306142216389L; + + /** {@inheritDoc} */ + @Override public Double fromDouble(double v) { + return v; + } + + /** {@inheritDoc} */ + @Override public double toDouble(Double v) { + assert v != null; + + return v; + } + + /** {@inheritDoc} */ + @Override public int hashCode() { + return Long.hashCode(serialVersionUID); + } + + /** {@inheritDoc} */ + @Override public boolean equals(Object o) { + if (this == o) + return true; + + if (o == null || getClass() != o.getClass()) + return false; + + return true; + } +}
http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/KeyMapper.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/KeyMapper.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/KeyMapper.java new file mode 100644 index 0000000..1ac2f3d --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/KeyMapper.java @@ -0,0 +1,33 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.io.Serializable; + +/** + * Maps key objects to index in {@link Vector} or {@link Matrix}. + */ +public interface KeyMapper<K> extends Serializable { + /** + * Checks given cache key corresponds to a valid index in vector or matrix. + * + * @param k Key to check. + * @return {@code true} if there is a valid index, {@code false} otherwise. + */ + public boolean isValid(K k); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/Matrix.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/Matrix.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/Matrix.java new file mode 100644 index 0000000..1039484 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/Matrix.java @@ -0,0 +1,518 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.io.Externalizable; +import org.apache.ignite.lang.IgniteUuid; +import org.apache.ignite.ml.math.exceptions.CardinalityException; +import org.apache.ignite.ml.math.exceptions.IndexException; +import org.apache.ignite.ml.math.exceptions.UnsupportedOperationException; +import org.apache.ignite.ml.math.functions.IgniteBiFunction; +import org.apache.ignite.ml.math.functions.IgniteDoubleFunction; +import org.apache.ignite.ml.math.functions.IgniteFunction; +import org.apache.ignite.ml.math.functions.IntIntToDoubleFunction; + +/** + * A matrix interface. + * + * Based on its flavor it can have vastly different implementations tailored for + * for different types of data (e.g. dense vs. sparse), different sizes of data or different operation + * optimizations. + * + * Note also that not all operations can be supported by all underlying implementations. If an operation is not + * supported a {@link UnsupportedOperationException} is thrown. This exception can also be thrown in partial cases + * where an operation is unsupported only in special cases, e.g. where a given operation cannot be deterministically + * completed in polynomial time. + * + * Based on ideas from <a href="http://mahout.apache.org/">Apache Mahout</a>. + */ +public interface Matrix extends MetaAttributes, Externalizable, StorageOpsMetrics, Destroyable { + /** + * Holder for matrix's element. + */ + interface Element { + /** + * Gets element's value. + * + * @return The value of this matrix element. + */ + double get(); + + /** + * Gets element's row index. + * + * @return The row index of this element. + */ + int row(); + + /** + * Gets element's column index. + * + * @return The column index of this element. + */ + int column(); + + /** + * Sets element's value. + * + * @param val Value to set. + */ + void set(double val); + } + + /** + * Gets the maximum value in this matrix. + * + * @return Maximum value in this matrix. + */ + public double maxValue(); + + /** + * Gets the minimum value in this matrix. + * + * @return Minimum value in this matrix. + */ + public double minValue(); + + /** + * Gets the maximum element in this matrix. + * + * @return Maximum element in this matrix. + */ + public Element maxElement(); + + /** + * Gets the minimum element in this matrix. + * + * @return Minimum element in this matrix. + */ + public Element minElement(); + + /** + * Gets the matrix's element at the given coordinates. + * + * @param row Row index. + * @param col Column index. + * @return Element at the given coordinates. + */ + public Element getElement(int row, int col); + + /** + * Swaps two rows in this matrix. + * + * @param row1 Row #1. + * @param row2 Row #2. + * @return This matrix. + */ + public Matrix swapRows(int row1, int row2); + + /** + * Swaps two columns in this matrix. + * + * @param col1 Column #1. + * @param col2 Column #2. + * @return This matrix. + */ + public Matrix swapColumns(int col1, int col2); + + /** + * Assigns given value to all elements of this matrix. + * + * @param val Value to assign to all elements. + * @return This matrix. + */ + public Matrix assign(double val); + + /** + * Assigns given values to this matrix. + * + * @param vals Values to assign. + * @return This matrix. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix assign(double[][] vals); + + /** + * Assigns values from given matrix to this matrix. + * + * @param mtx Matrix to assign to this matrix. + * @return This matrix. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix assign(Matrix mtx); + + /** + * Assigns each matrix element to the value generated by given function. + * + * @param fun Function that takes the row and column and returns the value to assign. + * @return This matrix. + */ + public Matrix assign(IntIntToDoubleFunction fun); + + /** + * Maps all values in this matrix through a given function. + * + * @param fun Mapping function. + * @return This matrix. + */ + public Matrix map(IgniteDoubleFunction<Double> fun); + + /** + * Maps all values in this matrix through a given function. + * + * For this matrix <code>A</code>, argument matrix <code>B</code> and the + * function <code>F</code> this method maps every cell <code>x, y</code> as: + * <code>A(x,y) = fun(A(x,y), B(x,y))</code> + * + * @param mtx Argument matrix. + * @param fun Mapping function. + * @return This function. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix map(Matrix mtx, IgniteBiFunction<Double, Double, Double> fun); + + /** + * Assigns values from given vector to the specified column in this matrix. + * + * @param col Column index. + * @param vec Vector to get values from. + * @return This matrix. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix assignColumn(int col, Vector vec); + + /** + * Assigns values from given vector to the specified row in this matrix. + * + * @param row Row index. + * @param vec Vector to get values from. + * @return This matrix. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix assignRow(int row, Vector vec); + + /** + * Collects the results of applying a given function to all rows in this matrix. + * + * @param fun Aggregating function. + * @return Vector of row aggregates. + */ + public Vector foldRows(IgniteFunction<Vector, Double> fun); + + /** + * Collects the results of applying a given function to all columns in this matrix. + * + * @param fun Aggregating function. + * @return Vector of column aggregates. + */ + public Vector foldColumns(IgniteFunction<Vector, Double> fun); + + /** + * Folds this matrix into a single value. + * + * @param foldFun Folding function that takes two parameters: accumulator and the current value. + * @param mapFun Mapping function that is called on each matrix cell before its passed to the accumulator (as its + * second parameter). + * @param <T> Type of the folded value. + * @param zeroVal Zero value for fold function. + * @return Folded value of this matrix. + */ + public <T> T foldMap(IgniteBiFunction<T, Double, T> foldFun, IgniteDoubleFunction<Double> mapFun, T zeroVal); + + /** + * Calculates the density of the matrix based on supplied criteria. + * Returns {@code true} if this matrix is denser than threshold with at least 80% confidence. + * + * @param threshold the threshold value [0, 1] of non-zero elements above which the matrix is considered dense. + */ + public boolean density(double threshold); + + /** + * Gets number of columns in this matrix. + * + * @return The number of columns in this matrix. + */ + public int columnSize(); + + /** + * Gets number of rows in this matrix. + * + * @return The number of rows in this matrix. + */ + public int rowSize(); + + /** + * Returns matrix determinant using Laplace theorem. + * + * @return A determinant for this matrix. + * @throws CardinalityException Thrown if matrix is not square. + */ + public double determinant(); + + /** + * Returns the inverse matrix of this matrix + * + * @return Inverse of this matrix + */ + public Matrix inverse(); + + /** + * Divides each value in this matrix by the argument. + * + * @param x Divider value. + * @return This matrix. + */ + public Matrix divide(double x); + + /** + * Gets the matrix value at the provided location. + * + * @param row Row index. + * @param col Column index. + * @return Matrix value. + * @throws IndexException Thrown in case of index is out of bound. + */ + public double get(int row, int col); + + /** + * Gets the matrix value at the provided location without checking boundaries. + * This method is marginally quicker than its {@link #get(int, int)} sibling. + * + * @param row Row index. + * @param col Column index. + * @return Matrix value. + */ + public double getX(int row, int col); + + /** + * Gets matrix storage model. + */ + public MatrixStorage getStorage(); + + /** + * Clones this matrix. + * + * NOTE: new matrix will have the same flavor as the this matrix but a different ID. + * + * @return New matrix of the same underlying class, the same size and the same values. + */ + public Matrix copy(); + + /** + * Creates new empty matrix of the same underlying class but of different size. + * + * NOTE: new matrix will have the same flavor as the this matrix but a different ID. + * + * @param rows Number of rows for new matrix. + * @param cols Number of columns for new matrix. + * @return New matrix of the same underlying class and size. + */ + public Matrix like(int rows, int cols); + + /** + * Creates new empty vector of compatible properties (similar or the same flavor) to this matrix. + * + * @param crd Cardinality of the vector. + * @return Newly created empty vector "compatible" to this matrix. + */ + public Vector likeVector(int crd); + + /** + * Creates new matrix where each value is a difference between corresponding value of this matrix and + * passed in argument matrix. + * + * @param mtx Argument matrix. + * @return New matrix of the same underlying class and size. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix minus(Matrix mtx); + + /** + * Creates new matrix where each value is a sum of the corresponding value of this matrix and + * argument value. + * + * @param x Value to add. + * @return New matrix of the same underlying class and size. + */ + public Matrix plus(double x); + + /** + * Creates new matrix where each value is a sum of corresponding values of this matrix and + * passed in argument matrix. + * + * @param mtx Argument matrix. + * @return New matrix of the same underlying class and size. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix plus(Matrix mtx); + + /** + * Auto-generated globally unique matrix ID. + * + * @return Matrix GUID. + */ + public IgniteUuid guid(); + + /** + * Sets given value. + * + * @param row Row index. + * @param col Column index. + * @param val Value to set. + * @return This matrix. + * @throws IndexException Thrown in case of either index is out of bound. + */ + public Matrix set(int row, int col, double val); + + /** + * Sets values for given row. + * + * @param row Row index. + * @param data Row data to set. + * @return This matrix. + * @throws IndexException Thrown in case of index is out of bound. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix setRow(int row, double[] data); + + /** + * Sets values for given column. + * + * @param col Column index. + * @param data Column data to set. + * @return This matrix. + * @throws IndexException Thrown in case of index is out of bound. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix setColumn(int col, double[] data); + + /** + * Sets given value without checking for index bounds. This method is marginally faster + * than its {@link #set(int, int, double)} sibling. + * + * @param row Row index. + * @param col Column index. + * @param val Value to set. + * @return This matrix. + */ + public Matrix setX(int row, int col, double val); + + /** + * Creates new matrix containing the product of given value and values in this matrix. + * + * @param x Value to multiply. + * @return New matrix. + */ + public Matrix times(double x); + + /** + * Creates new matrix that is the product of multiplying this matrix and the argument matrix. + * + * @param mtx Argument matrix. + * @return New matrix. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Matrix times(Matrix mtx); + + /** + * Creates new matrix that is the product of multiplying this matrix and the argument vector. + * + * @param vec Argument vector. + * @return New matrix. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector times(Vector vec); + + /** + * Gets maximum absolute row sum norm of this matrix. + * See http://mathworld.wolfram.com/MaximumAbsoluteRowSumNorm.html + * + * @return Maximum absolute row sum norm of this matrix. + */ + public double maxAbsRowSumNorm(); + + /** + * Gets sum of all elements in the matrix. + * + * @return Sum of all elements in this matrix. + */ + public double sum(); + + /** + * Creates new matrix that is transpose of this matrix. + * + * @return New transposed matrix. + */ + public Matrix transpose(); + + /** + * Creates new view into this matrix. Changes to the view will be propagated to this matrix. + * + * @param off View offset as <code>int[x,y]</code>. + * @param size View size as <code>int[rows, cols]</code> + * @return New view. + * @throws CardinalityException Thrown if cardinalities mismatch. + * @throws IndexException Thrown in case of offset is out of bound. + */ + public Matrix viewPart(int[] off, int[] size); + + /** + * Creates new view into this matrix. Changes to the view will be propagated to this matrix. + * + * @param rowOff + * @param rows + * @param colOff + * @param cols + * @return New view. + * @throws CardinalityException Thrown if cardinalities mismatch. + * @throws IndexException Thrown in case of offset is out of bound. + */ + public Matrix viewPart(int rowOff, int rows, int colOff, int cols); + + /** + * Creates new view into matrix row. Changes to the view will be propagated to this matrix. + * + * @param row Row index. + * @return New view. + * @throws IndexException Thrown in case of index is out of bound. + */ + public Vector viewRow(int row); + + /** + * Creates new view into matrix column . Changes to the view will be propagated to this matrix. + * + * @param col Column index. + * @return New view. + * @throws IndexException Thrown in case of index is out of bound. + */ + public Vector viewColumn(int col); + + /** + * Creates new view into matrix diagonal. Changes to the view will be propagated to this matrix. + * + * @return New view. + */ + public Vector viewDiagonal(); + + /** + * Destroys matrix if managed outside of JVM. It's a no-op in all other cases. + */ + public default void destroy() { + // No-op. + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixKeyMapper.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixKeyMapper.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixKeyMapper.java new file mode 100644 index 0000000..54d2088 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixKeyMapper.java @@ -0,0 +1,30 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +/** + * Maps {@link Matrix} row and column index to cache key. + */ +public interface MatrixKeyMapper<K> extends KeyMapper<K> { + /** + * @param x Matrix row index. + * @param y Matrix column index. + * @return Cache key for given row and column. + */ + public K apply(int x, int y); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixStorage.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixStorage.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixStorage.java new file mode 100644 index 0000000..ccfebe5 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/MatrixStorage.java @@ -0,0 +1,58 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.io.Externalizable; + +/** + * Data storage support for {@link Matrix}. + */ +public interface MatrixStorage extends Externalizable, StorageOpsMetrics, Destroyable { + /** + * @param x Matrix row index. + * @param y Matrix column index. + * @return Value corresponding to given row and column. + */ + public double get(int x, int y); + + /** + * @param x Matrix row index. + * @param y Matrix column index. + * @param v Value to set at given row and column. + */ + public void set(int x, int y, double v); + + /** + * + */ + public int columnSize(); + + /** + * + */ + public int rowSize(); + + /** + * Gets underlying array if {@link StorageOpsMetrics#isArrayBased()} returns {@code true}. + * + * @see StorageOpsMetrics#isArrayBased() + */ + default public double[][] data() { + return null; + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/MetaAttributes.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/MetaAttributes.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/MetaAttributes.java new file mode 100644 index 0000000..8befc6a --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/MetaAttributes.java @@ -0,0 +1,76 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.util.Map; + +/** + * Interface provides support for meta attributes on vectors and matrices. + */ +public interface MetaAttributes { + /** + * Implementation should return an instance of the map to store meta attributes. + */ + public Map<String, Object> getMetaStorage(); + + /** + * Gets meta attribute with given name. + * + * @param name Name of the vector meta attribute to get. + * @param <T> Attribute's type. + */ + @SuppressWarnings("unchecked") + public default <T> T getAttribute(String name) { + return (T)getMetaStorage().get(name); + } + + /** + * Sets meta attribute with given name and value. + * + * @param name Name of the meta attribute. + * @param val Attribute value. + * @param <T> Attribute's type. + */ + public default <T> void setAttribute(String name, T val) { + getMetaStorage().put(name, val); + } + + /** + * Removes meta attribute with given name. + * + * @param name Name of the meta attribute. + * @return {@code true} if attribute was present and was removed, {@code false} otherwise. + */ + public default boolean removeAttribute(String name) { + boolean is = getMetaStorage().containsKey(name); + + if (is) + getMetaStorage().remove(name); + + return is; + } + + /** + * Checks if given meta attribute is present. + * + * @param name Attribute name to check. + */ + public default boolean hasAttribute(String name) { + return getMetaStorage().containsKey(name); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/MurmurHash.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/MurmurHash.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/MurmurHash.java new file mode 100644 index 0000000..0cbcbdf --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/MurmurHash.java @@ -0,0 +1,246 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.nio.ByteBuffer; +import java.nio.ByteOrder; + +/** + * This is a very fast, non-cryptographic hash suitable for general hash-based lookup. + * + * See http://murmurhash.googlepages.com/ for mre details. + */ +public class MurmurHash { + /** Hide it. */ + private MurmurHash() { + } + + /** + * This produces exactly the same hash values as the final C+ version of MurmurHash3 and is + * thus suitable for producing the same hash values across platforms. + * + * The 32 bit x86 version of this hash should be the fastest variant for relatively short keys like IDs. + * + * Note - The x86 and x64 versions do _not_ produce the same results, as the algorithms are + * optimized for their respective platforms. + * + * See also http://github.com/yonik/java_util for future updates to this method. + * + * @param data + * @param off + * @param len + * @param seed + * @return 32 bit hash platform compatible with C++ MurmurHash3 implementation on x86. + */ + public static int hash3X86(byte[] data, int off, int len, int seed) { + int c1 = 0xcc9e2d51; + int c2 = 0x1b873593; + + int h1 = seed; + int roundedEnd = off + (len & 0xfffffffc); // Round down to 4 byte block. + + for (int i = off; i < roundedEnd; i += 4) { + int k1 = (data[i] & 0xff) | ((data[i + 1] & 0xff) << 8) | ((data[i + 2] & 0xff) << 16) | (data[i + 3] << 24); + + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); + k1 *= c2; + + h1 ^= k1; + h1 = (h1 << 13) | (h1 >>> 19); + h1 = h1 * 5 + 0xe6546b64; + } + + // Tail. + int k1 = 0; + + switch (len & 0x03) { + case 3: + k1 = (data[roundedEnd + 2] & 0xff) << 16; + // Fallthrough - WTF? + case 2: + k1 |= (data[roundedEnd + 1] & 0xff) << 8; + // Fallthrough - WTF? + case 1: + k1 |= data[roundedEnd] & 0xff; + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); + k1 *= c2; + h1 ^= k1; + default: + } + + // Finalization. + h1 ^= len; + + h1 ^= h1 >>> 16; + h1 *= 0x85ebca6b; + h1 ^= h1 >>> 13; + h1 *= 0xc2b2ae35; + h1 ^= h1 >>> 16; + + return h1; + } + + /** + * Hashes an int. + * + * @param data The int to hash. + * @param seed The seed for the hash. + * @return The 32 bit hash of the bytes in question. + */ + public static int hash(int data, int seed) { + byte[] arr = new byte[] { + (byte)(data >>> 24), + (byte)(data >>> 16), + (byte)(data >>> 8), + (byte)data + }; + + return hash(ByteBuffer.wrap(arr), seed); + } + + /** + * Hashes bytes in an array. + * + * @param data The bytes to hash. + * @param seed The seed for the hash. + * @return The 32 bit hash of the bytes in question. + */ + public static int hash(byte[] data, int seed) { + return hash(ByteBuffer.wrap(data), seed); + } + + /** + * Hashes bytes in part of an array. + * + * @param data The data to hash. + * @param off Where to start munging. + * @param len How many bytes to process. + * @param seed The seed to start with. + * @return The 32-bit hash of the data in question. + */ + public static int hash(byte[] data, int off, int len, int seed) { + return hash(ByteBuffer.wrap(data, off, len), seed); + } + + /** + * Hashes the bytes in a buffer from the current position to the limit. + * + * @param buf The bytes to hash. + * @param seed The seed for the hash. + * @return The 32 bit murmur hash of the bytes in the buffer. + */ + public static int hash(ByteBuffer buf, int seed) { + ByteOrder byteOrder = buf.order(); + buf.order(ByteOrder.LITTLE_ENDIAN); + + int m = 0x5bd1e995; + int r = 24; + + int h = seed ^ buf.remaining(); + + while (buf.remaining() >= 4) { + int k = buf.getInt(); + + k *= m; + k ^= k >>> r; + k *= m; + + h *= m; + h ^= k; + } + + if (buf.remaining() > 0) { + ByteBuffer finish = ByteBuffer.allocate(4).order(ByteOrder.LITTLE_ENDIAN); + + finish.put(buf).rewind(); + + h ^= finish.getInt(); + h *= m; + } + + h ^= h >>> 13; + h *= m; + h ^= h >>> 15; + + buf.order(byteOrder); + + return h; + } + + /** + * @param data + * @param seed + */ + public static long hash64A(byte[] data, int seed) { + return hash64A(ByteBuffer.wrap(data), seed); + } + + /** + * @param data + * @param off + * @param len + * @param seed + */ + public static long hash64A(byte[] data, int off, int len, int seed) { + return hash64A(ByteBuffer.wrap(data, off, len), seed); + } + + /** + * @param buf + * @param seed + */ + public static long hash64A(ByteBuffer buf, int seed) { + ByteOrder byteOrder = buf.order(); + buf.order(ByteOrder.LITTLE_ENDIAN); + + long m = 0xc6a4a7935bd1e995L; + int r = 47; + + long h = seed ^ (buf.remaining() * m); + + while (buf.remaining() >= 8) { + long k = buf.getLong(); + + k *= m; + k ^= k >>> r; + k *= m; + + h ^= k; + h *= m; + } + + if (buf.remaining() > 0) { + ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN); + + finish.put(buf).rewind(); + + h ^= finish.getLong(); + h *= m; + } + + h ^= h >>> r; + h *= m; + h ^= h >>> r; + + buf.order(byteOrder); + + return h; + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageConstants.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageConstants.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageConstants.java new file mode 100644 index 0000000..ec2ee65 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageConstants.java @@ -0,0 +1,49 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +/** + * Support for different modes of accessing data storage. + */ +public interface StorageConstants { + /** Storage mode optimized for sequential access. */ + public static final int SEQUENTIAL_ACCESS_MODE = 1001; + + /** Storage mode optimized for random access. */ + public static final int RANDOM_ACCESS_MODE = 1002; + + /** Storage mode optimized for row access. */ + public static final int ROW_STORAGE_MODE = 2001; + + /** Storage mode optimized for column access. */ + public static final int COLUMN_STORAGE_MODE = 2002; + + /** + * @param mode Access mode to verify. + */ + public default void assertAccessMode(int mode) { + assert mode == SEQUENTIAL_ACCESS_MODE || mode == RANDOM_ACCESS_MODE; + } + + /** + * @param mode Storage mode to verify. + */ + public default void assertStorageMode(int mode) { + assert mode == ROW_STORAGE_MODE || mode == COLUMN_STORAGE_MODE; + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageOpsMetrics.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageOpsMetrics.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageOpsMetrics.java new file mode 100644 index 0000000..aa39481 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/StorageOpsMetrics.java @@ -0,0 +1,49 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +/** + * Storage and operation cost characteristics. + */ +public interface StorageOpsMetrics { + /** + * Checks if this implementation should be considered to be iterable in index order in an efficient way. + */ + public boolean isSequentialAccess(); + + /** + * Checks if this implementation is optimized for random access. + */ + public boolean isRandomAccess(); + + /** + * Checks if this implementation should be considered dense so that it explicitly + * represents every value. + */ + public boolean isDense(); + + /** + * Checks if implementation is based on Java arrays. + */ + public boolean isArrayBased(); + + /** + * Checks whether implementation is JVM-local or distributed (multi-JVM). + */ + public boolean isDistributed(); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/Tracer.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/Tracer.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/Tracer.java new file mode 100644 index 0000000..007a8fe --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/Tracer.java @@ -0,0 +1,456 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.awt.Color; +import java.awt.Desktop; +import java.io.BufferedReader; +import java.io.BufferedWriter; +import java.io.File; +import java.io.FileWriter; +import java.io.IOException; +import java.io.InputStreamReader; +import java.nio.file.Files; +import java.nio.file.Paths; +import java.nio.file.StandardOpenOption; +import java.util.Locale; +import java.util.function.Function; +import java.util.stream.Collectors; +import org.apache.ignite.IgniteLogger; +import org.apache.ignite.lang.IgniteUuid; + +/** + * Utility methods to support output of {@link Vector} and {@link Matrix} instances to plain text or HTML. + */ +public class Tracer { + /** + * Double to color mapper. + */ + public interface ColorMapper extends Function<Double, Color> { + } + + /** Continuous red-to-blue color mapping. */ + static private ColorMapper defaultColorMapper(double min, double max) { + double range = max - min; + + return new ColorMapper() { + /** {@inheritDoc} */ + @Override public Color apply(Double d) { + int r = (int)Math.round(255 * d); + int g = 0; + int b = (int)Math.round(255 * (1 - d)); + + return new Color(r, g, b); + } + }; + } + + /** + * Default vector color mapper implementation that map given double value + * to continuous red-blue (R_B) specter. + * + * @param vec Vector to map. + * @return {@link ColorMapper} for the given vector. + */ + static private ColorMapper mkVectorColorMapper(Vector vec) { + return defaultColorMapper(vec.minValue(), vec.maxValue()); + } + + /** Default matrix color mapper implementation that map given double value + * to continuous red-blue (R_B) specter. + * @param mtx Matrix to be mapped. + * @return Color mapper for given matrix. + */ + static private ColorMapper mkMatrixColorMapper(Matrix mtx) { + return defaultColorMapper(mtx.minValue(), mtx.maxValue()); + } + + /** + * @param vec Vector to show. + * @param log {@link IgniteLogger} instance for output. + * @param fmt Format string for vector elements. + */ + public static void showAscii(Vector vec, IgniteLogger log, String fmt) { + String cls = vec.getClass().getSimpleName(); + + log.info(String.format("%s(%d) [%s]", cls, vec.size(), mkString(vec, fmt))); + } + + /** + * @param vec Vector to show as plain text. + * @param log {@link IgniteLogger} instance for output. + */ + public static void showAscii(Vector vec, IgniteLogger log) { + showAscii(vec, log, "%4f"); + } + + /** + * @param vec Vector to show as plain text. + * @param fmt Format string for vector elements. + */ + public static void showAscii(Vector vec, String fmt) { + String cls = vec.getClass().getSimpleName(); + + System.out.println(String.format("%s(%d) [%s]", cls, vec.size(), mkString(vec, fmt))); + } + + /** + * @param mtx Matrix to show as plain text. + */ + public static void showAscii(Matrix mtx) { + showAscii(mtx, "%4f"); + } + + /** + * @param mtx Matrix to show. + * @param row Matrix row to output. + * @param fmt Format string for matrix elements in the row. + * @return String representation of given matrix row according to given format. + */ + static private String rowStr(Matrix mtx, int row, String fmt) { + StringBuilder buf = new StringBuilder(); + + boolean first = true; + + int cols = mtx.columnSize(); + + for (int col = 0; col < cols; col++) { + String s = String.format(fmt, mtx.get(row, col)); + + if (!first) + buf.append(", "); + + buf.append(s); + + first = false; + } + + return buf.toString(); + } + + /** + * @param mtx {@link Matrix} object to show as a plain text. + * @param fmt Format string for matrix rows. + */ + public static void showAscii(Matrix mtx, String fmt) { + String cls = mtx.getClass().getSimpleName(); + + int rows = mtx.rowSize(); + int cols = mtx.columnSize(); + + System.out.println(String.format("%s(%dx%d)", cls, rows, cols)); + + for (int row = 0; row < rows; row++) + System.out.println(rowStr(mtx, row, fmt)); + } + + /** + * @param mtx {@link Matrix} object to show as a plain text. + * @param log {@link IgniteLogger} instance to output the logged matrix. + * @param fmt Format string for matrix rows. + */ + public static void showAscii(Matrix mtx, IgniteLogger log, String fmt) { + String cls = mtx.getClass().getSimpleName(); + + int rows = mtx.rowSize(); + int cols = mtx.columnSize(); + + log.info(String.format("%s(%dx%d)", cls, rows, cols)); + + for (int row = 0; row < rows; row++) + log.info(rowStr(mtx, row, fmt)); + } + + /** + * @param vec {@link Vector} object to show as a plain text. + */ + public static void showAscii(Vector vec) { + showAscii(vec, "%4f"); + } + + /** + * Saves given vector as CSV file. + * + * @param vec Vector to save. + * @param fmt Format to use. + * @param filePath Path of the file to save to. + */ + public static void saveAsCsv(Vector vec, String fmt, String filePath) throws IOException { + String s = mkString(vec, fmt); + + Files.write(Paths.get(filePath), s.getBytes(), StandardOpenOption.CREATE, StandardOpenOption.WRITE); + } + + /** + * Saves given matrix as CSV file. + * + * @param mtx Matrix to save. + * @param fmt Format to use. + * @param filePath Path of the file to save to. + */ + public static void saveAsCsv(Matrix mtx, String fmt, String filePath) throws IOException { + String s = mkString(mtx, fmt); + + Files.write(Paths.get(filePath), s.getBytes(), StandardOpenOption.CREATE, StandardOpenOption.WRITE); + } + + /** + * Shows given matrix in the browser with D3-based visualization. + * + * @param mtx Matrix to show. + * @throws IOException Thrown in case of any errors. + */ + public static void showHtml(Matrix mtx) throws IOException { + showHtml(mtx, mkMatrixColorMapper(mtx)); + } + + /** + * Shows given matrix in the browser with D3-based visualization. + * + * @param mtx Matrix to show. + * @param cm Optional color mapper. If not provided - red-to-blue (R_B) mapper will be used. + * @throws IOException Thrown in case of any errors. + */ + public static void showHtml(Matrix mtx, ColorMapper cm) throws IOException { + // Read it every time so that we can change it at runtime. + String tmpl = fileToString("d3-matrix-template.html"); + + String cls = mtx.getClass().getSimpleName(); + + double min = mtx.minValue(); + double max = mtx.maxValue(); + + openHtmlFile(tmpl. + replaceAll("/\\*@NAME@\\*/.*\n", "var name = \"" + cls + "\";\n"). + replaceAll("/\\*@MIN@\\*/.*\n", "var min = " + dataColorJson(min, cm.apply(min)) + ";\n"). + replaceAll("/\\*@MAX@\\*/.*\n", "var max = " + dataColorJson(max, cm.apply(max)) + ";\n"). + replaceAll("/\\*@DATA@\\*/.*\n", "var data = " + mkJsArrayString(mtx, cm) + ";\n") + ); + } + + /** + * Shows given vector in the browser with D3-based visualization. + * + * @param vec Vector to show. + * @throws IOException Thrown in case of any errors. + */ + public static void showHtml(Vector vec) throws IOException { + showHtml(vec, mkVectorColorMapper(vec)); + } + + /** + * @param d Value of {@link Matrix} or {@link Vector} element. + * @param clr {@link Color} to paint. + * @return JSON representation for given value and color. + */ + static private String dataColorJson(double d, Color clr) { + return "{" + + "d: " + String.format("%4f", d) + + ", r: " + clr.getRed() + + ", g: " + clr.getGreen() + + ", b: " + clr.getBlue() + + "}"; + } + + /** + * Shows given vector in the browser with D3-based visualization. + * + * @param vec Vector to show. + * @param cm Optional color mapper. If not provided - red-to-blue (R_B) mapper will be used. + * @throws IOException Thrown in case of any errors. + */ + public static void showHtml(Vector vec, ColorMapper cm) throws IOException { + // Read it every time so that we can change it at runtime. + String tmpl = fileToString("d3-vector-template.html"); + + String cls = vec.getClass().getSimpleName(); + + double min = vec.minValue(); + double max = vec.maxValue(); + + openHtmlFile(tmpl. + replaceAll("/\\*@NAME@\\*/.*\n", "var name = \"" + cls + "\";\n"). + replaceAll("/\\*@MIN@\\*/.*\n", "var min = " + dataColorJson(min, cm.apply(min)) + ";\n"). + replaceAll("/\\*@MAX@\\*/.*\n", "var max = " + dataColorJson(max, cm.apply(max)) + ";\n"). + replaceAll("/\\*@DATA@\\*/.*\n", "var data = " + mkJsArrayString(vec, cm) + ";\n") + ); + } + + /** + * Reads file content into the string. + * + * @param fileName Name of the file (on classpath) to read. + * @return Content of the file. + * @throws IOException If an I/O error of some sort has occurred. + */ + private static String fileToString(String fileName) throws IOException { + assert Tracer.class.getResourceAsStream(fileName) != null : "Can't get resource: " + fileName; + + InputStreamReader is = new InputStreamReader(Tracer.class.getResourceAsStream(fileName)); + + String str = new BufferedReader(is).lines().collect(Collectors.joining("\n")); + + is.close(); + + return str; + } + + /** + * Opens file in the browser with given HTML content. + * + * @param html HTML content. + * @throws IOException Thrown in case of any errors. + */ + static private void openHtmlFile(String html) throws IOException { + File temp = File.createTempFile(IgniteUuid.randomUuid().toString(), ".html"); + + BufferedWriter bw = new BufferedWriter(new FileWriter(temp)); + + bw.write(html); + + bw.close(); + + Desktop.getDesktop().browse(temp.toURI()); + } + + /** + * Gets string presentation of this vector. + * + * @param vec Vector to string-ify. + * @param fmt {@link String#format(Locale, String, Object...)} format. + */ + private static String mkString(Vector vec, String fmt) { + boolean first = true; + + StringBuilder buf = new StringBuilder(); + + for (Vector.Element x : vec.all()) { + String s = String.format(Locale.US, fmt, x.get()); + + if (!first) { + buf.append(", "); + buf.append(s); + } + else { + buf.append(s); + first = false; + } + } + + return buf.toString(); + } + + /** + * Gets JavaScript array presentation of this vector. + * + * @param vec Vector to JavaScript-ify. + * @param cm Color mapper to user. + */ + private static String mkJsArrayString(Vector vec, ColorMapper cm) { + boolean first = true; + + StringBuilder buf = new StringBuilder(); + + for (Vector.Element x : vec.all()) { + double d = x.get(); + + String s = dataColorJson(d, cm.apply(d)); + + if (!first) + buf.append(", "); + + buf.append(s); + + first = false; + } + + return '[' + buf.toString() + ']'; + } + + /** + * Gets JavaScript array presentation of this vector. + * + * @param mtx Matrix to JavaScript-ify. + * @param cm Color mapper to user. + */ + private static String mkJsArrayString(Matrix mtx, ColorMapper cm) { + boolean first = true; + + StringBuilder buf = new StringBuilder(); + + int rows = mtx.rowSize(); + int cols = mtx.columnSize(); + + for (int row = 0; row < rows; row++) { + StringBuilder rowBuf = new StringBuilder(); + + boolean rowFirst = true; + + for (int col = 0; col < cols; col++) { + double d = mtx.get(row, col); + + String s = dataColorJson(d, cm.apply(d)); + + if (!rowFirst) + rowBuf.append(", "); + + rowBuf.append(s); + + rowFirst = false; + } + + if (!first) + buf.append(", "); + + buf.append('[').append(rowBuf.toString()).append(']'); + + first = false; + } + + return '[' + buf.toString() + ']'; + } + + /** + * @param mtx Matrix to log. + * @param fmt Output format. + * @return Formatted representation of a matrix. + */ + private static String mkString(Matrix mtx, String fmt) { + StringBuilder buf = new StringBuilder(); + + int rows = mtx.rowSize(); + int cols = mtx.columnSize(); + + for (int row = 0; row < rows; row++) { + for (int col = 0; col < cols; col++) { + String s = String.format(Locale.US, fmt, mtx.get(row, col)); + + if (col != 0) + buf.append(", "); + + buf.append(s); + + if (col == cols - 1 && row != rows - 1) + buf.append(",\n"); + + } + } + + return buf.toString(); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/ValueMapper.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/ValueMapper.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/ValueMapper.java new file mode 100644 index 0000000..2b62c0b --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/ValueMapper.java @@ -0,0 +1,35 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.io.Serializable; + +/** + * Utility mapper that can be used to map arbitrary values types to and from double. + */ +public interface ValueMapper<V> extends Serializable { + /** + * @param v + */ + public V fromDouble(double v); + + /** + * @param v + */ + public double toDouble(V v); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/Vector.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/Vector.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/Vector.java new file mode 100644 index 0000000..b5e1d69 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/Vector.java @@ -0,0 +1,498 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.io.Externalizable; +import java.util.Spliterator; +import java.util.function.IntToDoubleFunction; +import org.apache.ignite.lang.IgniteUuid; +import org.apache.ignite.ml.math.exceptions.CardinalityException; +import org.apache.ignite.ml.math.exceptions.IndexException; +import org.apache.ignite.ml.math.exceptions.UnsupportedOperationException; +import org.apache.ignite.ml.math.functions.IgniteBiFunction; +import org.apache.ignite.ml.math.functions.IgniteDoubleFunction; + +/** + * A vector interface. + * + * Based on its flavor it can have vastly different implementations tailored for + * for different types of data (e.g. dense vs. sparse), different sizes of data or different operation + * optimizations. + * + * Note also that not all operations can be supported by all underlying implementations. If an operation is not + * supported a {@link UnsupportedOperationException} is thrown. This exception can also be thrown in partial cases + * where an operation is unsupported only in special cases, e.g. where a given operation cannot be deterministically + * completed in polynomial time. + * + * Based on ideas from <a href="http://mahout.apache.org/">Apache Mahout</a>. + */ +public interface Vector extends MetaAttributes, Externalizable, StorageOpsMetrics, Destroyable { + /** + * Holder for vector's element. + */ + interface Element { + /** + * Gets element's value. + * + * @return The value of this vector element. + */ + double get(); + + /** + * Gets element's index in the vector. + * + * @return The index of this vector element. + */ + int index(); + + /** + * Sets element's value. + * + * @param val Value to set. + */ + void set(double val); + } + + /** + * Gets cardinality of this vector (maximum number of the elements). + * + * @return This vector's cardinality. + */ + public int size(); + + /** + * Creates new copy of this vector. + * + * @return New copy vector. + */ + public Vector copy(); + + /** + * Gets iterator over all elements in this vector. + * + * NOTE: implementation can choose to reuse {@link Element} instance so you need to copy it + * if you want to retain it outside of iteration. + * + * @return Iterator. + */ + public Iterable<Element> all(); + + /** + * Iterates ove all non-zero elements in this vector. + * + * NOTE: implementation can choose to reuse {@link Element} instance so you need to copy it + * if you want to retain it outside of iteration. + * + * @return Iterator. + */ + public Iterable<Element> nonZeroes(); + + /** + * Gets spliterator for all values in this vector. + * + * @return Spliterator for all values. + */ + public Spliterator<Double> allSpliterator(); + + /** + * Gets spliterator for all non-zero values in this vector. + * + * @return Spliterator for all non-zero values. + */ + public Spliterator<Double> nonZeroSpliterator(); + + /** + * Sorts this vector in ascending order. + */ + public Vector sort(); + + /** + * Gets element at the given index. + * + * NOTE: implementation can choose to reuse {@link Element} instance so you need to copy it + * if you want to retain it outside of iteration. + * + * @param idx Element's index. + * @return Vector's element at the given index. + * @throws IndexException Throw if index is out of bounds. + */ + public Element getElement(int idx); + + /** + * Assigns given value to all elements of this vector. + * + * @param val Value to assign. + * @return This vector. + */ + public Vector assign(double val); + + /** + * Assigns values from given array to this vector. + * + * @param vals Values to assign. + * @return This vector. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector assign(double[] vals); + + /** + * Copies values from the argument vector to this one. + * + * @param vec Argument vector. + * @return This vector. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector assign(Vector vec); + + /** + * Assigns each vector element to the value generated by given function. + * + * @param fun Function that takes the index and returns value. + * @return This vector. + */ + public Vector assign(IntToDoubleFunction fun); + + /** + * Maps all values in this vector through a given function. + * + * @param fun Mapping function. + * @return This vector. + */ + public Vector map(IgniteDoubleFunction<Double> fun); + + /** + * Maps all values in this vector through a given function. + * + * For this vector <code>A</code>, argument vector <code>B</code> and the + * function <code>F</code> this method maps every element <code>x</code> as: + * <code>A(x) = F(A(x), B(x))</code> + * + * @param vec Argument vector. + * @param fun Mapping function. + * @return This function. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector map(Vector vec, IgniteBiFunction<Double, Double, Double> fun); + + /** + * Maps all elements of this vector by applying given function to each element with a constant + * second parameter <code>y</code>. + * + * @param fun Mapping function. + * @param y Second parameter for mapping function. + * @return This vector. + */ + public Vector map(IgniteBiFunction<Double, Double, Double> fun, double y); + + /** + * Creates new vector containing values from this vector divided by the argument. + * + * @param x Division argument. + * @return New vector. + */ + public Vector divide(double x); + + /** + * Gets dot product of two vectors. + * + * @param vec Argument vector. + * @return Dot product of two vectors. + */ + public double dot(Vector vec); + + /** + * Gets the value at specified index. + * + * @param idx Vector index. + * @return Vector value. + * @throws IndexException Throw if index is out of bounds. + */ + public double get(int idx); + + /** + * Gets the value at specified index without checking for index boundaries. + * + * @param idx Vector index. + * @return Vector value. + */ + public double getX(int idx); + + /** + * Creates new empty vector of the same underlying class but of different cardinality. + * + * @param crd Cardinality for new vector. + * @return New vector. + */ + public Vector like(int crd); + + /** + * Creates new matrix of compatible flavor with given size. + * + * @param rows Number of rows. + * @param cols Number of columns. + * @return New matrix. + */ + public Matrix likeMatrix(int rows, int cols); + + /** + * Converts this vector into [N x 1] or [1 x N] matrix where N is this vector cardinality. + * + * @param rowLike {@code true} for rowLike [N x 1], or {@code false} for column [1 x N] matrix. + * @return Newly created matrix. + */ + public Matrix toMatrix(boolean rowLike); + + /** + * Converts this vector into [N+1 x 1] or [1 x N+1] matrix where N is this vector cardinality. + * (0,0) element of this matrix will be {@code zeroVal} parameter. + * + * @param rowLike {@code true} for rowLike [N+1 x 1], or {@code false} for column [1 x N+1] matrix. + * @return Newly created matrix. + */ + public Matrix toMatrixPlusOne(boolean rowLike, double zeroVal); + + /** + * Creates new vector containing element by element difference between this vector and the argument one. + * + * @param vec Argument vector. + * @return New vector. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector minus(Vector vec); + + /** + * Creates new vector containing the normalized (L_2 norm) values of this vector. + * + * @return New vector. + */ + public Vector normalize(); + + /** + * Creates new vector containing the normalized (L_power norm) values of this vector. + * See http://en.wikipedia.org/wiki/Lp_space for details. + * + * @param power The power to use. Must be >= 0. May also be {@link Double#POSITIVE_INFINITY}. + * @return New vector {@code x} such that {@code norm(x, power) == 1} + */ + public Vector normalize(double power); + + /** + * Creates new vector containing the {@code log(1 + entry) / L_2 norm} values of this vector. + * + * @return New vector. + */ + public Vector logNormalize(); + + /** + * Creates new vector with a normalized value calculated as {@code log_power(1 + entry) / L_power norm}. + * + * @param power The power to use. Must be > 1. Cannot be {@link Double#POSITIVE_INFINITY}. + * @return New vector + */ + public Vector logNormalize(double power); + + /** + * Gets the k-norm of the vector. See http://en.wikipedia.org/wiki/Lp_space for more details. + * + * @param power The power to use. + * @see #normalize(double) + */ + public double kNorm(double power); + + /** + * Gets minimal value in this vector. + * + * @return Minimal value. + */ + public double minValue(); + + /** + * Gets maximum value in this vector. + * + * @return Maximum c. + */ + public double maxValue(); + + /** + * Gets minimal element in this vector. + * + * @return Minimal element. + */ + public Element minElement(); + + /** + * Gets maximum element in this vector. + * + * @return Maximum element. + */ + public Element maxElement(); + + /** + * Creates new vector containing sum of each element in this vector and argument. + * + * @param x Argument value. + * @return New vector. + */ + public Vector plus(double x); + + /** + * Creates new vector containing element by element sum from both vectors. + * + * @param vec Other argument vector to add. + * @return New vector. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector plus(Vector vec); + + /** + * Sets value. + * + * @param idx Vector index to set value at. + * @param val Value to set. + * @return This vector. + * @throws IndexException Throw if index is out of bounds. + */ + public Vector set(int idx, double val); + + /** + * Sets value without checking for index boundaries. + * + * @param idx Vector index to set value at. + * @param val Value to set. + * @return This vector. + */ + public Vector setX(int idx, double val); + + /** + * Increments value at given index without checking for index boundaries. + * + * @param idx Vector index. + * @param val Increment value. + * @return This vector. + */ + public Vector incrementX(int idx, double val); + + /** + * Increments value at given index. + * + * @param idx Vector index. + * @param val Increment value. + * @return This vector. + * @throws IndexException Throw if index is out of bounds. + */ + public Vector increment(int idx, double val); + + /** + * Gets number of non-zero elements in this vector. + * + * @return Number of non-zero elements in this vector. + */ + public int nonZeroElements(); + + /** + * Gets a new vector that contains product of each element and the argument. + * + * @param x Multiply argument. + * @return New vector. + */ + public Vector times(double x); + + /** + * Gets a new vector that is an element-wie product of this vector and the argument. + * + * @param vec Vector to multiply by. + * @return New vector. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public Vector times(Vector vec); + + /** + * @param off Offset into parent vector. + * @param len Length of the view. + */ + public Vector viewPart(int off, int len); + + /** + * Gets vector storage model. + */ + public VectorStorage getStorage(); + + /** + * Gets the sum of all elements in this vector. + * + * @return Vector's sum + */ + public double sum(); + + /** + * Gets the cross product of this vector and the other vector. + * + * @param vec Second vector. + * @return New matrix as a cross product of two vectors. + */ + public Matrix cross(Vector vec); + + /** + * Folds this vector into a single value. + * + * @param foldFun Folding function that takes two parameters: accumulator and the current value. + * @param mapFun Mapping function that is called on each vector element before its passed to the accumulator (as its + * second parameter). + * @param <T> Type of the folded value. + * @param zeroVal Zero value for fold operation. + * @return Folded value of this vector. + */ + public <T> T foldMap(IgniteBiFunction<T, Double, T> foldFun, IgniteDoubleFunction<Double> mapFun, T zeroVal); + + /** + * Combines & maps two vector and folds them into a single value. + * + * @param vec Another vector to combine with. + * @param foldFun Folding function. + * @param combFun Combine function. + * @param <T> Type of the folded value. + * @param zeroVal Zero value for fold operation. + * @return Folded value of these vectors. + * @throws CardinalityException Thrown when cardinalities mismatch. + */ + public <T> T foldMap(Vector vec, IgniteBiFunction<T, Double, T> foldFun, IgniteBiFunction<Double, Double, Double> combFun, + T zeroVal); + + /** + * Gets the sum of squares of all elements in this vector. + * + * @return Length squared value. + */ + public double getLengthSquared(); + + /** + * Get the square of the distance between this vector and the argument vector. + * + * @param vec Another vector. + * @return Distance squared. + * @throws CardinalityException Thrown if cardinalities mismatch. + */ + public double getDistanceSquared(Vector vec); + + /** + * Auto-generated globally unique vector ID. + * + * @return Vector GUID. + */ + public IgniteUuid guid(); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorKeyMapper.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorKeyMapper.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorKeyMapper.java new file mode 100644 index 0000000..4b8fadb --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorKeyMapper.java @@ -0,0 +1,29 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +/** + * Maps {@link Vector} element index to cache key. + */ +public interface VectorKeyMapper<K> extends KeyMapper<K> { + /** + * @param i Vector element index. + * @return Cache key for given element index. + */ + public K apply(int i); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorStorage.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorStorage.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorStorage.java new file mode 100644 index 0000000..3b66e4f --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/VectorStorage.java @@ -0,0 +1,53 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math; + +import java.io.Externalizable; + +/** + * Data storage support for {@link Vector}. + */ +public interface VectorStorage extends Externalizable, StorageOpsMetrics, Destroyable { + /** + * + * + */ + public int size(); + + /** + * @param i Vector element index. + * @return Value obtained for given element index. + */ + public double get(int i); + + /** + * @param i Vector element index. + * @param v Value to set at given index. + */ + public void set(int i, double v); + + /** + * Gets underlying array if {@link StorageOpsMetrics#isArrayBased()} returns {@code true}. + * Returns {@code null} if in other cases. + * + * @see StorageOpsMetrics#isArrayBased() + */ + public default double[] data() { + return null; + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/d78e071a/modules/ml/src/main/java/org/apache/ignite/ml/math/decompositions/CholeskyDecomposition.java ---------------------------------------------------------------------- diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/math/decompositions/CholeskyDecomposition.java b/modules/ml/src/main/java/org/apache/ignite/ml/math/decompositions/CholeskyDecomposition.java new file mode 100644 index 0000000..bc18307 --- /dev/null +++ b/modules/ml/src/main/java/org/apache/ignite/ml/math/decompositions/CholeskyDecomposition.java @@ -0,0 +1,306 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.ml.math.decompositions; + +import org.apache.ignite.ml.math.Matrix; +import org.apache.ignite.ml.math.Vector; +import org.apache.ignite.ml.math.exceptions.CardinalityException; +import org.apache.ignite.ml.math.exceptions.NonPositiveDefiniteMatrixException; +import org.apache.ignite.ml.math.exceptions.NonSymmetricMatrixException; + +/** + * Calculates the Cholesky decomposition of a matrix. + * + * This class inspired by class from Apache Common Math with similar name. + * + * @see <a href="http://mathworld.wolfram.com/CholeskyDecomposition.html">MathWorld</a> + * @see <a href="http://en.wikipedia.org/wiki/Cholesky_decomposition">Wikipedia</a> + */ +public class CholeskyDecomposition extends DecompositionSupport { + /** + * Default threshold above which off-diagonal elements are considered too different + * and matrix not symmetric. + */ + public static final double DFLT_REL_SYMMETRY_THRESHOLD = 1.0e-15; + + /** + * Default threshold below which diagonal elements are considered null + * and matrix not positive definite. + */ + public static final double DFLT_ABS_POSITIVITY_THRESHOLD = 1.0e-10; + + /** Row-oriented storage for L<sup>T</sup> matrix data. */ + private double[][] lTData; + /** Cached value of L. */ + private Matrix cachedL; + /** Cached value of LT. */ + private Matrix cachedLT; + /** Origin matrix */ + private Matrix origin; + + /** + * Calculates the Cholesky decomposition of the given matrix. + * + * Calling this constructor is equivalent to call {@link #CholeskyDecomposition(Matrix, double, double)} with the + * thresholds set to the default values {@link #DFLT_REL_SYMMETRY_THRESHOLD} and + * {@link #DFLT_ABS_POSITIVITY_THRESHOLD}. + * + * @param mtx the matrix to decompose. + * @throws CardinalityException if matrix is not square. + * @see #CholeskyDecomposition(Matrix, double, double) + * @see #DFLT_REL_SYMMETRY_THRESHOLD + * @see #DFLT_ABS_POSITIVITY_THRESHOLD + */ + public CholeskyDecomposition(final Matrix mtx) { + this(mtx, DFLT_REL_SYMMETRY_THRESHOLD, DFLT_ABS_POSITIVITY_THRESHOLD); + } + + /** + * Calculates the Cholesky decomposition of the given matrix. + * + * @param mtx the matrix to decompose. + * @param relSymmetryThreshold threshold above which off-diagonal elements are considered too different and matrix + * not symmetric + * @param absPositivityThreshold threshold below which diagonal elements are considered null and matrix not positive + * definite + * @see #CholeskyDecomposition(Matrix) + * @see #DFLT_REL_SYMMETRY_THRESHOLD + * @see #DFLT_ABS_POSITIVITY_THRESHOLD + */ + public CholeskyDecomposition(final Matrix mtx, final double relSymmetryThreshold, + final double absPositivityThreshold) { + assert mtx != null; + + if (mtx.columnSize() != mtx.rowSize()) + throw new CardinalityException(mtx.rowSize(), mtx.columnSize()); + + origin = mtx; + + final int order = mtx.rowSize(); + + lTData = toDoubleArr(mtx); + cachedL = null; + cachedLT = null; + + // Check the matrix before transformation. + for (int i = 0; i < order; ++i) { + final double[] lI = lTData[i]; + + // Check off-diagonal elements (and reset them to 0). + for (int j = i + 1; j < order; ++j) { + final double[] lJ = lTData[j]; + + final double lIJ = lI[j]; + final double lJI = lJ[i]; + + final double maxDelta = relSymmetryThreshold * Math.max(Math.abs(lIJ), Math.abs(lJI)); + + if (Math.abs(lIJ - lJI) > maxDelta) + throw new NonSymmetricMatrixException(i, j, relSymmetryThreshold); + + lJ[i] = 0; + } + } + + // Transform the matrix. + for (int i = 0; i < order; ++i) { + final double[] ltI = lTData[i]; + + // Check diagonal element. + if (ltI[i] <= absPositivityThreshold) + throw new NonPositiveDefiniteMatrixException(ltI[i], i, absPositivityThreshold); + + ltI[i] = Math.sqrt(ltI[i]); + final double inverse = 1.0 / ltI[i]; + + for (int q = order - 1; q > i; --q) { + ltI[q] *= inverse; + final double[] ltQ = lTData[q]; + + for (int p = q; p < order; ++p) + ltQ[p] -= ltI[q] * ltI[p]; + } + } + } + + /** */ + @Override public void destroy() { + if (cachedL != null) + cachedL.destroy(); + if (cachedLT != null) + cachedLT.destroy(); + } + + /** + * Returns the matrix L of the decomposition. + * <p>L is an lower-triangular matrix</p> + * + * @return the L matrix + */ + public Matrix getL() { + if (cachedL == null) + cachedL = getLT().transpose(); + + return cachedL; + } + + /** + * Returns the transpose of the matrix L of the decomposition. + * <p>L<sup>T</sup> is an upper-triangular matrix</p> + * + * @return the transpose of the matrix L of the decomposition + */ + public Matrix getLT() { + + if (cachedLT == null) { + Matrix like = like(origin, origin.rowSize(), origin.columnSize()); + like.assign(lTData); + + cachedLT = like; + } + + // return the cached matrix + return cachedLT; + } + + /** + * Return the determinant of the matrix + * + * @return determinant of the matrix + */ + public double getDeterminant() { + double determinant = 1.0; + + for (int i = 0; i < lTData.length; ++i) { + double lTii = lTData[i][i]; + determinant *= lTii * lTii; + } + + return determinant; + } + + /** + * Solve the linear equation A × X = B for matrices A. + * + * @param b right-hand side of the equation A × X = B + * @return a vector X that minimizes the two norm of A × X - B + * @throws CardinalityException if the vectors dimensions do not match + */ + public Vector solve(final Vector b) { + final int m = lTData.length; + + if (b.size() != m) + throw new CardinalityException(b.size(), m); + + final double[] x = b.getStorage().data(); + + // Solve LY = b + for (int j = 0; j < m; j++) { + final double[] lJ = lTData[j]; + + x[j] /= lJ[j]; + + final double xJ = x[j]; + + for (int i = j + 1; i < m; i++) + x[i] -= xJ * lJ[i]; + } + + // Solve LTX = Y + for (int j = m - 1; j >= 0; j--) { + x[j] /= lTData[j][j]; + + final double xJ = x[j]; + + for (int i = 0; i < j; i++) + x[i] -= xJ * lTData[i][j]; + } + + return likeVector(origin, m).assign(x); + } + + /** + * Solve the linear equation A × X = B for matrices A. + * + * @param b right-hand side of the equation A × X = B + * @return a matrix X that minimizes the two norm of A × X - B + * @throws CardinalityException if the matrices dimensions do not match + */ + public Matrix solve(final Matrix b) { + final int m = lTData.length; + + if (b.rowSize() != m) + throw new CardinalityException(b.rowSize(), m); + + final int nColB = b.columnSize(); + final double[][] x = b.getStorage().data(); + + // Solve LY = b + for (int j = 0; j < m; j++) { + final double[] lJ = lTData[j]; + final double lJJ = lJ[j]; + final double[] xJ = x[j]; + + for (int k = 0; k < nColB; ++k) + xJ[k] /= lJJ; + + for (int i = j + 1; i < m; i++) { + final double[] xI = x[i]; + final double lJI = lJ[i]; + + for (int k = 0; k < nColB; ++k) + xI[k] -= xJ[k] * lJI; + } + } + + // Solve LTX = Y + for (int j = m - 1; j >= 0; j--) { + final double lJJ = lTData[j][j]; + final double[] xJ = x[j]; + + for (int k = 0; k < nColB; ++k) + xJ[k] /= lJJ; + + for (int i = 0; i < j; i++) { + final double[] xI = x[i]; + final double lIJ = lTData[i][j]; + + for (int k = 0; k < nColB; ++k) + xI[k] -= xJ[k] * lIJ; + } + } + + return like(origin, m, b.columnSize()).assign(x); + } + + /** */ + private double[][] toDoubleArr(Matrix mtx) { + if (mtx.isArrayBased()) + return mtx.getStorage().data(); + + double[][] res = new double[mtx.rowSize()][]; + + for (int row = 0; row < mtx.rowSize(); row++) { + res[row] = new double[mtx.columnSize()]; + for (int col = 0; col < mtx.columnSize(); col++) + res[row][col] = mtx.get(row, col); + } + + return res; + } +}