001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math4.field.linalg;
018
019import java.util.Arrays;
020import java.util.List;
021import java.util.ArrayList;
022import org.apache.commons.numbers.field.Field;
023import org.apache.commons.math4.linear.AnyMatrix;
024
025/**
026 * Square matrix whose elements define a {@link Field}.
027 *
028 * @param <T> Type of the field elements.
029 *
030 * @since 4.0
031 */
032public class FieldDenseMatrix<T>
033    implements AnyMatrix {
034    /** Field. */
035    private final Field<T> field;
036    /** Number of rows. */
037    private final int rows;
038    /** Number of columns. */
039    private final int columns;
040    /** Data storage (in row-major order). */
041    private final T[] data;
042
043    /**
044     * @param f Field.
045     * @param r Number of rows.
046     * @param c Number of columns.
047     * @throws IllegalArgumentException if {@code r <= 0} or {@code c <= 0}.
048     */
049    protected FieldDenseMatrix(Field<T> f,
050                               int r,
051                               int c) {
052        if (r <= 0 ||
053            c <= 0) {
054            throw new IllegalArgumentException("Negative size");
055        }
056
057        field = f;
058        rows = r;
059        columns = c;
060        data = (T[]) new Object[r * c];
061    }
062
063    /**
064     * Factory method.
065     *
066     * @param <T> Type of the field elements.
067     * @param f Field.
068     * @param r Number of rows.
069     * @param c Number of columns.
070     * @return a new instance.
071     * @throws IllegalArgumentException if {@code r <= 0} or {@code c <= 0}.
072     */
073    public static <T> FieldDenseMatrix<T> create(Field<T> f,
074                                                 int r,
075                                                 int c) {
076        return new FieldDenseMatrix<>(f, r, c);
077    }
078
079    /**
080     * Factory method.
081     *
082     * @param <T> Type of the field elements.
083     * @param f Field.
084     * @param r Number of rows.
085     * @param c Number of columns.
086     * @return a matrix with elements zet to {@link Field#zero() zero}.
087     * @throws IllegalArgumentException if {@code r <= 0} or {@code c <= 0}.
088     */
089    public static <T> FieldDenseMatrix<T> zero(Field<T> f,
090                                               int r,
091                                               int c) {
092        return create(f, r, c).fill(f.zero());
093    }
094
095    /**
096     * Factory method.
097     *
098     * @param <T> Type of the field elements.
099     * @param f Field.
100     * @param n Dimension of the matrix.
101     * @throws IllegalArgumentException if {@code n <= 0}.
102     * @return the identity matrix.
103     */
104    public static <T> FieldDenseMatrix<T> identity(Field<T> f,
105                                                   int n) {
106        final FieldDenseMatrix<T> r = zero(f, n, n);
107
108        for (int i = 0; i < n; i++) {
109            r.set(i, i, f.one());
110        }
111
112        return r;
113    }
114
115    /** {@inheritDoc} */
116    @Override
117    public boolean equals(Object other) {
118        if (this == other) {
119            return true;
120        } else {
121            if (other instanceof FieldDenseMatrix) {
122                final FieldDenseMatrix<?> m = (FieldDenseMatrix<?>) other;
123                return field.equals(m.field) &&
124                    rows == m.rows &&
125                    columns == m.columns &&
126                    Arrays.equals(data, m.data);
127            } else {
128                return false;
129            }
130        }
131    }
132
133    /**
134     * Copies this matrix.
135     *
136     * @return a new instance.
137     */
138    public FieldDenseMatrix<T> copy() {
139        final FieldDenseMatrix<T> r = create(field, rows, columns);
140        System.arraycopy(data, 0, r.data, 0, data.length);
141        return r;
142    }
143
144    /**
145     * Transposes this matrix.
146     *
147     * @return a new instance.
148     */
149    public FieldDenseMatrix<T> transpose() {
150        final FieldDenseMatrix<T> r = create(field, columns, rows);
151
152        for (int i = 0; i < rows; i++) {
153            for (int j = 0; j < columns; j++) {
154                r.set(j, i, get(i, j));
155            }
156        }
157
158        return r;
159    }
160
161    /** {@inheritDoc} */
162    @Override
163    public int getRowDimension() {
164        return rows;
165    }
166
167    /** {@inheritDoc} */
168    @Override
169    public int getColumnDimension() {
170        return columns;
171    }
172
173    /**
174     * @return the field associated with the matrix entries.
175     */
176    public Field<T> getField() {
177        return field;
178    }
179
180    /**
181     * Sets all elements to the given value.
182     *
183     * @param value Value of the elements of the matrix.
184     * @return {@code this}.
185     */
186    public FieldDenseMatrix<T> fill(T value) {
187        Arrays.fill(data, value);
188        return this;
189    }
190
191    /**
192     * Gets an element.
193     *
194     * @param i Row.
195     * @param j Column.
196     * @return the element at (i, j).
197     */
198    public T get(int i,
199                 int j) {
200        return data[i * columns + j];
201    }
202
203    /**
204     * Sets an element.
205     *
206     * @param i Row.
207     * @param j Column.
208     * @param value Value.
209     */
210    public void set(int i,
211                    int j,
212                    T value) {
213        data[i * columns + j] = value;
214    }
215
216    /**
217     * Addition.
218     *
219     * @param other Matrix to add.
220     * @return a new instance with the result of the addition.
221     * @throws IllegalArgumentException if the dimensions do not match.
222     */
223    public FieldDenseMatrix<T> add(FieldDenseMatrix<T> other) {
224        checkAdd(other);
225        final FieldDenseMatrix<T> r = create(field, rows, columns);
226
227        for (int i = 0; i < data.length; i++) {
228            r.data[i] = field.add(data[i], other.data[i]);
229        }
230
231        return r;
232    }
233
234    /**
235     * Subtraction.
236     *
237     * @param other Matrix to subtract.
238     * @return a new instance with the result of the subtraction.
239     * @throws IllegalArgumentException if the dimensions do not match.
240     */
241    public FieldDenseMatrix<T> subtract(FieldDenseMatrix<T> other) {
242        checkAdd(other);
243        final FieldDenseMatrix<T> r = create(field, rows, columns);
244
245        for (int i = 0; i < data.length; i++) {
246            r.data[i] = field.subtract(data[i], other.data[i]);
247        }
248
249        return r;
250    }
251
252    /**
253     * Negate.
254     *
255     * @return a new instance with the opposite matrix.
256     */
257    public FieldDenseMatrix<T> negate() {
258        final FieldDenseMatrix<T> r = create(field, rows, columns);
259
260        for (int i = 0; i < data.length; i++) {
261            r.data[i] = field.negate(data[i]);
262        }
263
264        return r;
265    }
266
267    /**
268     * Multiplication.
269     *
270     * @param other Matrix to multiply with.
271     * @return a new instance with the result of the multiplication.
272     * @throws IllegalArgumentException if the dimensions do not match.
273     */
274    public FieldDenseMatrix<T> multiply(FieldDenseMatrix<T> other) {
275        checkMultiply(other);
276        final FieldDenseMatrix<T> r = zero(field, rows, other.columns);
277
278        for (int i = 0; i < rows; i++) {
279            final int o1 = i * columns;
280            final int o2 = i * r.columns;
281            for (int j = 0; j < other.columns; j++) {
282                final int o3 = o2 + j;
283                for (int k = 0; k < columns; k++) {
284                    r.data[o3] = field.add(r.data[o3],
285                                           field.multiply(data[o1 + k],
286                                                          other.data[k * other.columns + j]));
287                }
288            }
289        }
290
291        return r;
292    }
293
294    /**
295     * Multiplies the matrix with itself {@code p} times.
296     *
297     * @param p Exponent.
298     * @return a new instance.
299     * @throws IllegalArgumentException if {@code p < 0}.
300     */
301    public FieldDenseMatrix<T> pow(int p) {
302        checkMultiply(this);
303
304        if (p < 0) {
305            throw new IllegalArgumentException("Negative exponent: " + p);
306        }
307
308        if (p == 0) {
309            return identity(field, rows);
310        }
311
312        if (p == 1) {
313            return copy();
314        }
315
316        final int power = p - 1;
317
318        // Only log_2(p) operations are necessary by doing as follows:
319        //    5^214 = 5^128 * 5^64 * 5^16 * 5^4 * 5^2
320        // The same approach is used for A^p.
321
322        final char[] binary = Integer.toBinaryString(power).toCharArray();
323        final ArrayList<Integer> nonZeroPositions = new ArrayList<>();
324
325        for (int i = 0; i < binary.length; i++) {
326            if (binary[i] == '1') {
327                final int pos = binary.length - i - 1;
328                nonZeroPositions.add(pos);
329            }
330        }
331
332        final List<FieldDenseMatrix<T>> results = new ArrayList<>(binary.length);
333        results.add(this);
334        for (int i = 1; i < binary.length; i++) {
335            final FieldDenseMatrix<T> s = results.get(i - 1);
336            final FieldDenseMatrix<T> r = s.multiply(s);
337            results.add(r);
338        }
339
340        FieldDenseMatrix<T> r = this;
341        for (Integer i : nonZeroPositions) {
342            r = r.multiply(results.get(i));
343        }
344
345        return r;
346    }
347
348    /** {@inheritDoc} */
349    @Override
350    public int hashCode() {
351        assert false : "hashCode not designed";
352        return 42; // Any arbitrary constant will do.
353    }
354}