This is an automated email from the ASF dual-hosted git repository. erans pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-math.git
commit 128523112bdbad85b6b5c925004c0e975be5d553 Author: Gilles Sadowski <[email protected]> AuthorDate: Sun Oct 27 14:59:19 2019 +0100 MATH-1499: Matrix whose entries are elements of a field. --- .../math4/field/linalg/FieldDenseMatrix.java | 343 +++++++++++++++++++++ .../commons/math4/field/linalg/package-info.java | 21 ++ .../apache/commons/math4/field/package-info.java | 22 ++ .../field/linalg/FP64FieldDenseMatrixTest.java | 285 +++++++++++++++++ 4 files changed, 671 insertions(+) diff --git a/src/main/java/org/apache/commons/math4/field/linalg/FieldDenseMatrix.java b/src/main/java/org/apache/commons/math4/field/linalg/FieldDenseMatrix.java new file mode 100644 index 0000000..8fd0dc1 --- /dev/null +++ b/src/main/java/org/apache/commons/math4/field/linalg/FieldDenseMatrix.java @@ -0,0 +1,343 @@ +/* + * 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.commons.math4.field.linalg; + +import java.util.Arrays; +import java.util.List; +import java.util.ArrayList; +import org.apache.commons.numbers.field.Field; +import org.apache.commons.math4.linear.AnyMatrix; + +/** + * Square matrix whose elements define a {@link Field}. + * + * @param <T> Type of the field elements. + * + * @since 4.0 + */ +public class FieldDenseMatrix<T> + implements AnyMatrix { + /** Field. */ + private final Field<T> field; + /** Number of rows. */ + private final int rows; + /** Number of columns. */ + private final int columns; + /** Data storage (in row-major order). */ + private final T[] data; + + /** + * @param f Field. + * @param r Number of rows. + * @param c Number of columns. + * @throws IllegalArgumentException if {@code r <= 0} or {@code c <= 0}. + */ + protected FieldDenseMatrix(Field<T> f, + int r, + int c) { + if (r <= 0 || + c <= 0) { + throw new IllegalArgumentException("Negative size"); + } + + field = f; + rows = r; + columns = c; + data = (T[]) new Object[r * c]; + } + + /** + * Factory method. + * + * @param f Field. + * @param r Number of rows. + * @param c Number of columns. + * @throws IllegalArgumentException if {@code r <= 0} or {@code c <= 0}. + */ + public static <T> FieldDenseMatrix<T> create(Field<T> f, + int r, + int c) { + return new FieldDenseMatrix<>(f, r, c); + } + + /** + * Factory method. + * + * @param f Field. + * @param r Number of rows. + * @param c Number of columns. + * @throws IllegalArgumentException if {@code r <= 0} or {@code c <= 0}. + * @return a matrix with elements zet to {@link Field#zero() zero}. + */ + public static <T> FieldDenseMatrix<T> zero(Field<T> f, + int r, + int c) { + return create(f, r, c).fill(f.zero()); + } + + /** + * Factory method. + * + * @param f Field. + * @param n Dimension of the matrix. + * @return the identity matrix. + * @throws IllegalArgumentException if {@code n <= 0}. + */ + public static <T> FieldDenseMatrix<T> identity(Field<T> f, + int n) { + final FieldDenseMatrix<T> r = zero(f, n, n); + + for (int i = 0; i < n; i++) { + r.set(i, i, f.one()); + } + + return r; + } + + /** {@inheritDoc} */ + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } else { + if (other instanceof FieldDenseMatrix) { + final FieldDenseMatrix<?> m = (FieldDenseMatrix<?>) other; + return field.equals(m.field) && + rows == m.rows && + columns == m.columns && + Arrays.equals(data, m.data); + } else { + return false; + } + } + } + + /** + * Copies this matrix. + * + * @return a new instance. + */ + public FieldDenseMatrix<T> copy() { + final FieldDenseMatrix<T> r = create(field, rows, columns); + System.arraycopy(data, 0, r.data, 0, data.length); + return r; + } + + /** + * Transposes this matrix. + * + * @return a new instance. + */ + public FieldDenseMatrix<T> transpose() { + final FieldDenseMatrix<T> r = create(field, columns, rows); + + for (int i = 0; i < rows; i++) { + for (int j = 0; j < columns; j++) { + r.set(j, i, get(i, j)); + } + } + + return r; + } + + /** {@inheritDoc} */ + @Override + public int getRowDimension() { + return rows; + } + + /** {@inheritDoc} */ + @Override + public int getColumnDimension() { + return columns; + } + + /** + * @return the field associated with the matrix entries. + */ + public Field<T> getField() { + return field; + } + + /** + * Sets all elements to the given value. + * + * @param value Value of the elements of the matrix. + * @return {@code this}. + */ + public FieldDenseMatrix<T> fill(T value) { + Arrays.fill(data, value); + return this; + } + + /** + * Gets an element. + * + * @param i Row. + * @param j Column. + * @return the element at (i, j). + */ + public T get(int i, + int j) { + return data[i * columns + j]; + } + + /** + * Sets an element. + * + * @param i Row. + * @param j Column. + * @param value Value. + */ + public void set(int i, + int j, + T value) { + data[i * columns + j] = value; + } + + /** + * Addition. + * + * @param other Matrix to add. + * @return a new instance with the result of the addition. + * @throws IllegalArgumentException if the dimensions do not match. + */ + public FieldDenseMatrix<T> add(FieldDenseMatrix<T> other) { + checkAdd(other); + final FieldDenseMatrix<T> r = create(field, rows, columns); + + for (int i = 0; i < data.length; i++) { + r.data[i] = field.add(data[i], other.data[i]); + } + + return r; + } + + /** + * Subtraction. + * + * @param other Matrix to subtract. + * @return a new instance with the result of the subtraction. + * @throws IllegalArgumentException if the dimensions do not match. + */ + public FieldDenseMatrix<T> subtract(FieldDenseMatrix<T> other) { + checkAdd(other); + final FieldDenseMatrix<T> r = create(field, rows, columns); + + for (int i = 0; i < data.length; i++) { + r.data[i] = field.subtract(data[i], other.data[i]); + } + + return r; + } + + /** + * Negate. + * + * @return a new instance with the opposite matrix. + */ + public FieldDenseMatrix<T> negate() { + final FieldDenseMatrix<T> r = create(field, rows, columns); + + for (int i = 0; i < data.length; i++) { + r.data[i] = field.negate(data[i]); + } + + return r; + } + + /** + * Multiplication. + * + * @param other Matrix to multiply with. + * @return a new instance with the result of the multiplication. + * @throws IllegalArgumentException if the dimensions do not match. + */ + public FieldDenseMatrix<T> multiply(FieldDenseMatrix<T> other) { + checkMultiply(other); + final FieldDenseMatrix<T> r = zero(field, rows, other.columns); + + for (int i = 0; i < rows; i++) { + final int o1 = i * columns; + final int o2 = i * r.columns; + for (int j = 0; j < other.columns; j++) { + final int o3 = o2 + j; + for (int k = 0; k < columns; k++) { + r.data[o3] = field.add(r.data[o3], + field.multiply(data[o1 + k], + other.data[k * other.columns + j])); + } + } + } + + return r; + } + + /** + * Multiplies the matrix with itself {@code p} times. + * + * @param p Exponent. + * @return a new instance. + * @throws IllegalArgumentException if {@code p < 0}. + */ + public FieldDenseMatrix<T> pow(int p) { + checkMultiply(this); + + if (p < 0) { + throw new IllegalArgumentException("Negative exponent: " + p); + } + + if (p == 0) { + return identity(field, rows); + } + + if (p == 1) { + return copy(); + } + + final int power = p - 1; + + // Only log_2(p) operations are necessary by doing as follows: + // 5^214 = 5^128 * 5^64 * 5^16 * 5^4 * 5^2 + // The same approach is used for A^p. + + final char[] binary = Integer.toBinaryString(power).toCharArray(); + final ArrayList<Integer> nonZeroPositions = new ArrayList<>(); + + for (int i = 0; i < binary.length; i++) { + if (binary[i] == '1') { + final int pos = binary.length - i - 1; + nonZeroPositions.add(pos); + } + } + + final List<FieldDenseMatrix<T>> results = new ArrayList<>(binary.length); + results.add(this); + for (int i = 1; i < binary.length; i++) { + final FieldDenseMatrix<T> s = results.get(i - 1); + final FieldDenseMatrix<T> r = s.multiply(s); + results.add(r); + } + + FieldDenseMatrix<T> r = this; + for (Integer i : nonZeroPositions) { + r = r.multiply(results.get(i)); + } + + return r; + } +} diff --git a/src/main/java/org/apache/commons/math4/field/linalg/package-info.java b/src/main/java/org/apache/commons/math4/field/linalg/package-info.java new file mode 100644 index 0000000..3ee0946 --- /dev/null +++ b/src/main/java/org/apache/commons/math4/field/linalg/package-info.java @@ -0,0 +1,21 @@ +/* + * 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. + */ +/** + * Linear algebra defined in term of matrices whose entries are elements + * of a {@link org.apache.commons.numbers.field.Field field}. + */ +package org.apache.commons.math4.field.linalg; diff --git a/src/main/java/org/apache/commons/math4/field/package-info.java b/src/main/java/org/apache/commons/math4/field/package-info.java new file mode 100644 index 0000000..f800a67 --- /dev/null +++ b/src/main/java/org/apache/commons/math4/field/package-info.java @@ -0,0 +1,22 @@ +/* + * 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. + */ +/** + * Utilities based on the {@link org.apache.commons.numbers.field.Field Field} + * functionality defined in <a href="http://commons.apache.org/numbers";> + * Commons Numbers</a>. + */ +package org.apache.commons.math4.field; diff --git a/src/test/java/org/apache/commons/math4/field/linalg/FP64FieldDenseMatrixTest.java b/src/test/java/org/apache/commons/math4/field/linalg/FP64FieldDenseMatrixTest.java new file mode 100644 index 0000000..55a1ea2 --- /dev/null +++ b/src/test/java/org/apache/commons/math4/field/linalg/FP64FieldDenseMatrixTest.java @@ -0,0 +1,285 @@ +/* + * 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.commons.math4.field.linalg; + +import org.junit.Assert; +import org.junit.Test; +import org.apache.commons.numbers.field.FP64; +import org.apache.commons.numbers.field.FP64Field; +import org.apache.commons.math3.linear.RealMatrix; +import org.apache.commons.math3.linear.Array2DRowRealMatrix; +import org.apache.commons.math3.util.Pair; + +/** + * Tests for {@link FieldDenseMatrix} (using {@link FP64} as field elements). + */ +public class FP64FieldDenseMatrixTest { + @Test + public void testGetRowDimension() { + final int r = 6; + final int c = 9; + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), r, c); + Assert.assertEquals(r, a.getRowDimension()); + } + + @Test + public void testGetColumnDimension() { + final int r = 6; + final int c = 9; + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), r, c); + Assert.assertEquals(c, a.getColumnDimension()); + } + + @Test + public void testSetGet() { + final int r = 17; + final int c = 20; + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), r, c); + + int count = 0; + for (int i = 0; i < r; i++) { + for (int j = 0; j < c; j++) { + a.set(i, j, FP64.of(count++)); + } + } + Assert.assertEquals(r * c, count); + + count = 0; + for (int i = 0; i < r; i++) { + for (int j = 0; j < c; j++) { + Assert.assertEquals((double) count++, + a.get(i, j).doubleValue(), + 0d); + } + } + } + + @Test + public void testAdd() { + final int r = 5; + final int c = 3; + final double scale = 1e3; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p1 = createRandom(r, c, scale); + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p2 = createRandom(r, c, scale); + + assertEquals(p1.getFirst().add(p2.getFirst()), + p1.getSecond().add(p2.getSecond()), + 0d); + } + + @Test + public void testSubtract() { + final int r = 2; + final int c = 6; + final double scale = 1e3; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p1 = createRandom(r, c, scale); + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p2 = createRandom(r, c, scale); + + assertEquals(p1.getFirst().subtract(p2.getFirst()), + p1.getSecond().subtract(p2.getSecond()), + 0d); + } + + @Test + public void testMultiply() { + final int r = 7; + final int c1 = 4; + final int c2 = 5; + final double scale = 1e2; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p1 = createRandom(r, c1, scale); + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p2 = createRandom(c1, c2, scale); + + assertEquals(p1.getFirst().multiply(p2.getFirst()), + p1.getSecond().multiply(p2.getSecond()), + 0d); + } + + @Test + public void testNegate() { + final int dim = 13; + final double scale = 1; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p = createRandom(dim, dim, scale); + + assertEquals(p.getFirst().negate(), + p.getSecond().scalarMultiply(-1), + 0d); + } + + @Test + public void testPowZero() { + final int dim = 5; + final double scale = 1e100; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p = createRandom(dim, dim, scale); + + final int exp = 0; + assertEquals(p.getFirst().pow(exp), + p.getSecond().power(exp), + 0d); + } + + @Test + public void testPowOne() { + final int dim = 5; + final double scale = 1e100; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p = createRandom(dim, dim, scale); + + final int exp = 1; + assertEquals(p.getFirst().pow(exp), + p.getSecond().power(exp), + 0d); + } + + @Test + public void testPow() { + final int dim = 5; + final double scale = 1e2; + final Pair<FieldDenseMatrix<FP64>, RealMatrix> p = createRandom(dim, dim, scale); + + final int exp = 4; + assertEquals(p.getFirst().pow(exp), + p.getSecond().power(exp), + 0d); + } + + @Test + public void testGetField() { + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), 7, 5); + Assert.assertEquals(FP64Field.get(), a.getField()); + } + + @Test + public void testEquals() { + // Reference equality. + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), 7, 2); + Assert.assertEquals(a, a); + + // Dimension mismatch + final FieldDenseMatrix<FP64> b = FieldDenseMatrix.create(FP64Field.get(), 7, 3); + Assert.assertNotEquals(a, b); + final FieldDenseMatrix<FP64> c = FieldDenseMatrix.create(FP64Field.get(), 6, 2); + Assert.assertNotEquals(a, c); + + // Contents. + final FieldDenseMatrix<FP64> d = FieldDenseMatrix.create(FP64Field.get(), 7, 2); + Assert.assertEquals(a, d); // Unitialized contents. + a.fill(FP64.of(1.23456789)); + d.fill(FP64.of(1.23456789)); + Assert.assertEquals(a, d); // Initialized contents. + d.set(6, 1, d.get(6, 1).add(FP64.of(1e-15))); + Assert.assertNotEquals(a, d); + } + + @Test + public void testCopy() { + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), 7, 3) + .fill(FP64Field.get().one()); + final FieldDenseMatrix<FP64> b = a.copy(); + Assert.assertEquals(a, b); + + b.set(0, 0, FP64Field.get().zero()); + Assert.assertNotEquals(a, b); + } + + @Test + public void testTranspose() { + final int r = 4; + final int c = 5; + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), r, c); + for (int i = 0; i < r; i++) { + for (int j = 0; j < c; j++) { + final double j2 = j * j; + a.set(i, j, + FP64.of(1.2 * i + 3.4 * j2)); + } + } + + final FieldDenseMatrix<FP64> b = a.transpose(); + for (int i = 0; i < r; i++) { + for (int j = 0; j < c; j++) { + Assert.assertEquals(a.get(i, j), b.get(j, i)); + } + } + + Assert.assertEquals(a, b.transpose()); + } + + @Test + public void testIdentity() { + final int dim = 3; + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.identity(FP64Field.get(), dim); + for (int i = 0; i < dim; i++) { + for (int j = 0; j < dim; j++) { + if (i == j) { + Assert.assertEquals(FP64Field.get().one(), a.get(i, j)); + } else { + Assert.assertEquals(FP64Field.get().zero(), + a.get(i, j)); + } + } + } + } + + /** + * Compares with result obtained from "Commons Math". + * + * @param a "o.a.c.m.field.linalg" result. + * @param b "o.a.c.m.linear" result. + * @param tol Tolerance. + */ + private void assertEquals(FieldDenseMatrix<FP64> a, + RealMatrix b, + double tol) { + if (a.getRowDimension() != b.getRowDimension() || + a.getColumnDimension() != b.getColumnDimension()) { + Assert.fail("Dimension mismatch"); + } + + for (int i = 0; i < a.getRowDimension(); i++) { + for (int j = 0; j < a.getColumnDimension(); j++) { + Assert.assertEquals("(" + i + ", " + j + ")", + a.get(i, j).doubleValue(), + b.getEntry(i, j), + tol); + } + } + } + + /** + * Creates test matrices with random entries. + * + * @param r Rows. + * @param c Columns. + * @param scale Range of the entries. + * @return a pair of matrices whose entries are in the interval + * {@code [-scale, scale]}. + */ + private Pair<FieldDenseMatrix<FP64>, RealMatrix> createRandom(int r, + int c, + double scale) { + final FieldDenseMatrix<FP64> a = FieldDenseMatrix.create(FP64Field.get(), r, c); + final RealMatrix b = new Array2DRowRealMatrix(r, c); + for (int i = 0; i < r; i++) { + for (int j = 0; j < c; j++) { + final double v = scale * (2 * Math.random() - 1); + a.set(i, j, FP64.of(v)); + b.setEntry(i, j, v); + } + } + + return new Pair<>(a, b); + } +}
