SharedMeatAxe  1.0
zmu - Multiply
See also
zpt - Paste

Command Line

zmu [Options] [-r Row[/NRows]] [-c Col[/NCols]] A B Result 
Options
Standard options, see Standard Command Line Options
-r Row[/NRows]
Divide the matrix A horizontally into NRows slices (default: 2) and use the Row-th slice as the left factor. NRows must not be larger than the number of rows of A.
-c Col[/NCols]
Divide the matrix B vertically into NCols slices (default: 2) and use the Col-th slice as right factor. NCols must not be larger than the number of columns of B.
A
Left factor.
B
Right factor.
Result
Product.

Input Files

A
Left factor.
B
Right factor.

Output Files

Result
Product.

Description

This program reads two matrices or permutations and writes their product to Result.

The input files must contain two compatible objects, i.e., their product must be defined. Currently, zmu can handle the following data types:

  • Both files are matrices over the same field, and the number of columns of A equals the number of rows of B. In this case, zmu calculates the standard matrix product.
  • One of the operands is a one by one matrix, and the other is any matrix over the same field. In this case, the one by one matrix is interpreted as a scalar, and the program calculates the corresponding multiple of the matrix.
  • Both input files are permutations of degree a and b, respectively. The result is a permutation C of degree max(a,b), which is defined by C(x) = B(A(x)). If the permutations are of different degrees, the smaller permutation is extended to the larger degree by adding fixed points.
  • A is a matrix, B is a permutation and the degree of the permutation equals the number of columns of the matrix. The result is a matrix of the same size which is calculated from the input matrix by permuting the marks of each row in the following way: The i-th mark of the row is stored as the k-th mark of the result if the permutation maps i to k.
  • A is a permutation of degree m, and B is a m by n matrix. The result is again a m by n matrix which consists of the rows of the input matrix, rearranged according to the permutation. If the permutation maps i to k, then the k-th row of the input matrix becomes the i-th row of the output matrix. Here is an example:
                | 1 1 |     | 2 2 |
    (1 2 3)  *  | 2 2 |  =  | 3 3 |
                | 3 3 |     | 1 1 |
    

With these conventions, products between matrices and permutations are defined in a consistent way. The associative law a(bc)=(ab)c holds whenever ab and bc are defined (a,b,c being matrices or permutations). A permutation matrix created with zcv or zcf, if multiplied with another matrix, produces the same result as the original permutation.

Blockwise Matrix Multiplication

In the case of two matrices, a blockwise multiplication can be performed using the "-r" and "-c" options. If one or both of these options are specified on the command line, zmu will read only some rows of A and/or some columns of B. Multiplying the two pieces together yields a rectangular piece of the result. By default the result is divided into 4 pieces of (almost) equal size. To calculate the 4 pieces successively, type

zmu -r 1 -c 1 m1 m2 tmp11
zmu -r 1 -c 2 m1 m2 tmp12
zmu -r 2 -c 1 m1 m2 tmp21
zmu -r 2 -c 2 m1 m2 tmp22

The resulting matrices `tmpXX' can then be pasted together using zpt:

zpt -R 2 -C 2 result tmp

This procedure can be used in a multi-processor environment where each piece of the result is computed on a separate machine.

By adding an additional parameter to "-r" and/or "-c" you can control the number of vertical or horizontal slices. For example,

zmu -r 3/5

means to cut A horizontally into five slices and use the third slice for multiplication. The number of slice must not be greater than the number of rows.

Implementation Details

This program uses schoolbook multiplication. Asymptotically fast Winograd-Strassen multiplication (

See also
MatMulStrassen) is not used.

SharedMeatAxe 1.0 documentation, generated on Sat Dec 30 2017 12:13:21