Module: sage.matrix.strassen
Generic Asymptotically Fast Strassen Algorithms
SAGE implements asymptotically fast echelon form and matrix multiplication algorithms.
Module-level Functions
) |
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:
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
Author: Robert Bradshaw
) |
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. The following matrix dimensions are chosen especially to exercise the eight possible parity combinations that ocould ccur 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
Author: David Harvey
Class: int_range
Functions: intervals,
to_list
Special Functions: __add__,
__init__,
__iter__,
__len__,
__mul__,
__repr__,
__sub__
) |
) |
) |
) |
) |
) |
) |
See About this document... for information on suggesting changes.