This implementation is specially designed to be cache-friendly. Square blocks are stored as small arrays and allow efficient traversal of data both in row major direction and columns major direction, one block at a time. This greatly increases performances for algorithms that use crossed directions loops like multiplication or transposition.
The size of square blocks is a static parameter. It may be tuned according to the cache size of the target computer processor. As a rule of thumbs, it should be the largest value that allows three blocks to be simultaneously cached (this is necessary for example for matrix multiplication). The default value is to use 36x36 blocks.
The regular blocks represent BLOCK_SIZE x BLOCK_SIZE squares. Blocks
at right hand side and bottom side which may be smaller to fit matrix dimensions. The square
blocks are flattened in row major order in single dimension arrays which are therefore
BLOCK_SIZE2 elements long for regular blocks. The blocks are themselves
organized in row major order.
As an example, for a block size of 36x36, a 100x60 matrix would be stored in 6 blocks. Block 0 would be a Field[1296] array holding the upper left 36x36 square, block 1 would be a Field[1296] array holding the upper center 36x36 square, block 2 would be a Field[1008] array holding the upper right 36x28 rectangle, block 3 would be a Field[864] array holding the lower left 24x36 rectangle, block 4 would be a Field[864] array holding the lower center 24x36 rectangle and block 5 would be a Field[672] array holding the lower right 24x28 rectangle.
The layout complexity overhead versus simple mapping of matrices to java arrays is negligible for small matrices (about 1%). The gain from cache efficiency leads to up to 3-fold improvements for matrices of moderate to large size.
| Modifier and Type | Field and Description |
|---|---|
| public static final int | BLOCK_SIZE
Block size. |
| private final int | blockColumns
Number of block columns of the matrix. |
| private final int | blockRows
Number of block rows of the matrix. |
| private final T[][] | blocks
Blocks of matrix entries. |
| private final int | columns
Number of columns of the matrix. |
| private final int | rows
Number of rows of the matrix. |
| private static final long | serialVersionUID
Serializable version identifier. |
| Access | Constructor and Description |
|---|---|
| public | BlockFieldMatrix(final Field<T>
Field to which the elements belong. field, final int Number of rows in the new matrix. rows, final int Number of columns in the new matrix. columns)Create a new matrix with the supplied row and column dimensions. |
| public | BlockFieldMatrix(final T[][]
Data for the new matrix, in raw layout. rawData)Create a new dense matrix copying entries from raw layout data. |
| public | BlockFieldMatrix(final int
the number of rows in the new matrix rows, final int the number of columns in the new matrix columns, final T[][] data for new matrix blockData, final boolean if true, the input array will be copied, otherwise
it will be referenced copyArray)Create a new dense matrix copying entries from block layout data. |
| Modifier and Type | Method and Description |
|---|---|
| public FieldMatrix | add(final FieldMatrix<T>
Matrix to be added. m)Overrides org. Implements org. Compute the sum of this and m. |
| public BlockFieldMatrix | |
| public void | addToEntry(final int
Row location of entry to be set. row, final int Column location of entry to be set. column, final T Value to add to the current matrix entry in
increment)(row, column).Implements abstract org. Implements org. Change an entry in the specified row and column. |
| private int | Returns: height (number of rows) of the blockrow index (in block sense) of the block blockRow)Get the height of a block. |
| private int | Returns: width (number of columns) of the blockcolumn index (in block sense) of the block blockColumn)Get the width of a block. |
| public FieldMatrix | copy()
Implements abstract org. Implements org. Make a (deep) copy of this. |
| private void | copyBlockPart(final T[]
source block srcBlock, final int source block width ( srcWidth, final int BLOCK_SIZE or smaller)start row in the source block srcStartRow, final int end row (exclusive) in the source block srcEndRow, final int start column in the source block srcStartColumn, final int end column (exclusive) in the source block srcEndColumn, final T[] destination block dstBlock, final int destination block width ( dstWidth, final int BLOCK_SIZE or smaller)start row in the destination block dstStartRow, final int start column in the destination block dstStartColumn)Copy a part of a block into another one This method can be called only when the specified part fits in both blocks, no verification is done here. |
| public static < Type of the field elements. T extends FieldElement | Returns: a new data array in blocks layout.Field to which the elements belong. field, final int Number of rows in the new matrix. rows, final int Number of columns in the new matrix. columns)Create a data array in blocks layout. |
| public FieldMatrix | createMatrix(final int
the number of rows in the new matrix rowDimension, final int the number of columns in the new matrix columnDimension)Implements abstract org. Implements org. Create a new FieldMatrix<t> of the same type as the instance with the supplied row and column dimensions. |
| public T[] | getColumn(final int
the column to be fetched column)Overrides org. Implements org. Get the entries in column number |
| public int | getColumnDimension()
Implements abstract org. Implements org. Returns the number of columns in the matrix. |
| public FieldMatrix | getColumnMatrix(final int
Column to be fetched. column)Overrides org. Implements org. Get the entries in column number |
| public FieldVector | getColumnVector(final int
Column to be fetched. column)Overrides org. Implements org. Returns the entries in column number |
| public T[][] | getData()
Overrides org. Implements org. Returns matrix entries as a two-dimensional array. |
| public T | getEntry(final int
row location of entry to be fetched row, final int column location of entry to be fetched column)Implements abstract org. Implements org. Returns the entry in the specified row and column. |
| public T[] | getRow(final int
Row to be fetched. row)Overrides org. Implements org. Get the entries in row number |
| public int | getRowDimension()
Implements abstract org. Implements org. Returns the number of rows in the matrix. |
| public FieldMatrix | getRowMatrix(final int
Row to be fetched. row)Overrides org. Implements org. Get the entries in row number |
| public FieldVector | getRowVector(final int
Row to be fetched row)Overrides org. Implements org. Get the entries in row number |
| public FieldMatrix | getSubMatrix(final int
Initial row index startRow, final int Final row index (inclusive) endRow, final int Initial column index startColumn, final int Final column index (inclusive) endColumn)Overrides org. Implements org. Get a submatrix. |
| public FieldMatrix | multiply(final FieldMatrix<T>
Matrix to postmultiply by. m)Overrides org. Implements org. Postmultiply this matrix by |
| public BlockFieldMatrix | Returns: this * mmatrix to postmultiply by m)Returns the result of postmultiplying |
| public void | multiplyEntry(final int
Row location of entry to be set. row, final int Column location of entry to be set. column, final T Multiplication factor for the current matrix entry
in factor)(row,column)Implements abstract org. Implements org. Change an entry in the specified row and column. |
| public T[] | operate(final T[]
the vector to operate on v)Overrides org. Implements org. Returns the result of multiplying this by the vector |
| public T[] | preMultiply(final T[]
the row vector to premultiply by v)Overrides org. Implements org. Returns the (row) vector result of premultiplying this by the vector
|
| public FieldMatrix | scalarAdd(final T
Value to be added to each entry. d)Overrides org. Implements org. Increment each entry of this matrix. |
| public FieldMatrix | scalarMultiply(final T
Value to multiply all entries by. d)Overrides org. Implements org. Multiply each entry by |
| public void | setColumn(final int
the column to be set column, final T[] column array (must have the same number of rows as the instance) array)Overrides org. Implements org. Set the entries in column number |
| public void | setColumnMatrix(final int
Column to be set. column, final FieldMatrix<T> column matrix (must have one column and the same
number of rows as the instance). matrix)Overrides org. Implements org. Set the entries in column number |
| pack-priv void | setColumnMatrix(final int
Column to be set. column, final BlockFieldMatrix<T> Column matrix (must have one column and the same number of rows
as the instance). matrix)Sets the entries in column number |
| public void | setColumnVector(final int
Column to be set. column, final FieldVector<T> Column vector (must have the same number of rows
as the instance). vector)Overrides org. Implements org. Set the entries in column number |
| public void | setEntry(final int
row location of entry to be set row, final int column location of entry to be set column, final T matrix entry to be set in row,column value)Implements abstract org. Implements org. Set the entry in the specified row and column. |
| public void | setRow(final int
Row to be set. row, final T[] Row matrix (must have the same number of columns as
the instance). array)Overrides org. Implements org. Set the entries in row number |
| public void | setRowMatrix(final int
Row to be set. row, final FieldMatrix<T> Row matrix (must have one row and the same number
of columns as the instance). matrix)Overrides org. Implements org. Set the entries in row number |
| public void | setRowMatrix(final int
the row to be set row, final BlockFieldMatrix<T> row matrix (must have one row and the same number of columns
as the instance) matrix)Sets the entries in row number |
| public void | setRowVector(final int
Row to be set. row, final FieldVector<T> row vector (must have the same number of columns
as the instance). vector)Overrides org. Implements org. Set the entries in row number |
| public void | setSubMatrix(final T[][]
Array containing the submatrix replacement data. subMatrix, final int Row coordinate of the top-left element to be replaced. row, final int Column coordinate of the top-left element to be replaced. column)Overrides org. Implements org. Replace the submatrix starting at |
| public FieldMatrix | subtract(final FieldMatrix<T>
Matrix to be subtracted. m)Overrides org. Implements org. Subtract |
| public BlockFieldMatrix | |
| public static < Type of the field elements. T extends FieldElement | Returns: a new data array containing the same entries but in blocks layoutData array in raw layout. rawData)Convert a data array from raw layout to blocks layout. |
| public FieldMatrix | transpose()
Overrides org. Implements org. Returns the transpose of this matrix. |
| public T | walkInOptimizedOrder(final FieldMatrixChangingVisitor<T>
visitor used to process all matrix entries visitor)Overrides org. Implements org. Visit (and possibly change) all matrix entries using the fastest possible order. |
| public T | walkInOptimizedOrder(final FieldMatrixPreservingVisitor<T>
visitor used to process all matrix entries visitor)Overrides org. Implements org. Visit (but don't change) all matrix entries using the fastest possible order. |
| public T | walkInOptimizedOrder(final FieldMatrixChangingVisitor<T>
visitor used to process all matrix entries visitor, final int Initial row index startRow, final int Final row index (inclusive) endRow, final int Initial column index startColumn, final int Final column index (inclusive) endColumn)Overrides org. Implements org. Visit (and possibly change) some matrix entries using the fastest possible order. |
| public T | walkInOptimizedOrder(final FieldMatrixPreservingVisitor<T>
visitor used to process all matrix entries visitor, final int Initial row index startRow, final int Final row index (inclusive) endRow, final int Initial column index startColumn, final int Final column index (inclusive) endColumn)Overrides org. Implements org. Visit (but don't change) some matrix entries using the fastest possible order. |
| public T | walkInRowOrder(final FieldMatrixChangingVisitor<T>
visitor used to process all matrix entries visitor)Overrides org. Implements org. Visit (and possibly change) all matrix entries in row order. |
| public T | walkInRowOrder(final FieldMatrixPreservingVisitor<T>
visitor used to process all matrix entries visitor)Overrides org. Implements org. Visit (but don't change) all matrix entries in row order. |
| public T | walkInRowOrder(final FieldMatrixChangingVisitor<T>
visitor used to process all matrix entries visitor, final int Initial row index startRow, final int Final row index (inclusive) endRow, final int Initial column index startColumn, final int Final column index endColumn)Overrides org. Implements org. Visit (and possibly change) some matrix entries in row order. |
| public T | walkInRowOrder(final FieldMatrixPreservingVisitor<T>
visitor used to process all matrix entries visitor, final int Initial row index startRow, final int Final row index (inclusive) endRow, final int Initial column index startColumn, final int Final column index endColumn)Overrides org. Implements org. Visit (but don't change) some matrix entries in row order. |