Sage implements asymptotically fast echelon form and matrix multiplication algorithms.
Represent a list of integers as a list of integer intervals.
Note
Repetitions are not considered.
Useful class for dealing with pivots in the strassen echelon, could have much more general application
INPUT:
It can be one of the following:
OR
OR
OUTPUT:
An instance of int_range, i.e. a list of pairs (start, length).
EXAMPLES:
From a pair of integers:
sage: from sage.matrix.strassen import int_range
sage: int_range(2, 4)
[(2, 4)]
Default:
sage: int_range()
[]
From a list of integers:
sage: int_range([1,2,3,4])
[(1, 4)]
sage: int_range([1,2,3,4,6,7,8])
[(1, 4), (6, 3)]
sage: int_range([1,2,3,4,100,101,102])
[(1, 4), (100, 3)]
sage: int_range([1,1000,2,101,3,4,100,102])
[(1, 4), (100, 3), (1000, 1)]
Repetitions are not considered:
sage: int_range([1,2,3])
[(1, 3)]
sage: int_range([1,1,1,1,2,2,2,3])
[(1, 3)]
AUTHORS:
Return the list of intervals.
OUTPUT:
A list of pairs of integers.
EXAMPLES:
sage: from sage.matrix.strassen import int_range
sage: I = int_range([4,5,6,20,21,22,23])
sage: I.intervals()
[(4, 3), (20, 4)]
sage: type(I.intervals())
<type 'list'>
Return the (sorted) list of integers represented by this object.
OUTPUT:
A list of integers.
EXAMPLES:
sage: from sage.matrix.strassen import int_range
sage: I = int_range([6,20,21,4,5,22,23])
sage: I.to_list()
[4, 5, 6, 20, 21, 22, 23]
sage: I = int_range(34, 9)
sage: I.to_list()
[34, 35, 36, 37, 38, 39, 40, 41, 42]
Repetitions are not considered:
sage: I = int_range([1,1,1,1,2,2,2,3])
sage: I.to_list()
[1, 2, 3]
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:
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) #indirect doctest
sage: B == C
True
AUTHORS:
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) #indirect doctest
True
AUTHORS:
INPUT:
EXAMPLES:
sage: from sage.matrix.strassen import test
sage: for n in range(5): print n, test(2*n,n,Frac(QQ['x']),2)
0 True
1 True
2 True
3 True
4 True