Generic Asymptotically Fast Strassen Algorithms

Sage implements asymptotically fast echelon form and matrix multiplication algorithms.

class sage.matrix.strassen.int_range

Useful class for dealing with pivots in the strassen echelon, could have much more general application

AUTHORS:

• Robert Bradshaw

intervals()

to_list()

sage.matrix.strassen.strassen_echelon(A, cutoff)

Compute echelon form, in place. Internal function, call with M.echelonize(algorithm=”strassen”) Based on work of Robert Bradshaw and David Harvey at MSRI workshop in 2006.

INPUT:

• A - matrix window
• cutoff - size at which algorithm reverts to naive Gaussian elimination and multiplication must be at least 1.

OUTPUT: The list of pivot columns

EXAMPLE:

sage: A = matrix(QQ, 7, [5, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 3, 1, 0, -1, 0, 0, -1, 0, 1, 2, -1, 1, 0, -1, 0, 1, 3, -1, 1, 0, 0, -2, 0, 2, 0, 1, 0, 0, -1, 0, 1, 0, 1])
sage: B = A.__copy__(); B._echelon_strassen(1); B
[ 1  0  0  0  0  0  0]
[ 0  1  0 -1  0  1  0]
[ 0  0  1  0  0  0  0]
[ 0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  1]
[ 0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0]
sage: C = A.__copy__(); C._echelon_strassen(2); C == B
True
sage: C = A.__copy__(); C._echelon_strassen(4); C == B
True

sage: n = 32; A = matrix(Integers(389),n,range(n^2))
sage: B = A.__copy__(); B._echelon_in_place_classical()
sage: C = A.__copy__(); C._echelon_strassen(2)
sage: B == C
True

TESTS:

sage: A = matrix(Integers(7), 4, 4, [1,2,0,3,0,0,1,0,0,1,0,0,0,0,0,1])
sage: B = A.__copy__(); B._echelon_in_place_classical()
sage: C = A.__copy__(); C._echelon_strassen(2)
sage: B == C
True

sage: A = matrix(Integers(7), 4, 4, [1,0,5,0,2,0,3,6,5,1,2,6,4,6,1,1])
sage: B = A.__copy__(); B._echelon_in_place_classical()
sage: C = A.__copy__(); C._echelon_strassen(2)
sage: B == C
True

AUTHORS:

• Robert Bradshaw

sage.matrix.strassen.strassen_window_multiply(C, A, B, cutoff)

Multiplies the submatrices specified by A and B, places result in C. Assumes that A and B have compatible dimensions to be multiplied, and that C is the correct size to receive the product, and that they are all defined over the same ring.

Uses strassen multiplication at high levels and then uses MatrixWindow methods at low levels. EXAMPLES: The following matrix dimensions are chosen especially to exercise the eight possible parity combinations that could occur while subdividing the matrix in the strassen recursion. The base case in both cases will be a (4x5) matrix times a (5x6) matrix.

sage: A = MatrixSpace(Integers(2^65), 64, 83).random_element()
sage: B = MatrixSpace(Integers(2^65), 83, 101).random_element()
sage: A._multiply_classical(B) == A._multiply_strassen(B, 3)
True

AUTHORS:

• David Harvey