Generic Asymptotically Fast Strassen Algorithms¶

This implements asymptotically fast echelon form and matrix multiplication algorithms.

class sage.matrix.strassen.int_range(indices=None, range=None)[source]¶

Bases: object

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:

indices – integer; start of the unique interval
range – integer; length of the unique interval

indices – list of integers, the integers to wrap into intervals

indices – None (default), shortcut for an empty list

OUTPUT:

An instance of int_range, i.e. a list of pairs (start, length).

EXAMPLES:

From a pair of integers:

Sage

sage: from sage.matrix.strassen import int_range
sage: int_range(2, 4)
[(2, 4)]

Python

>>> from sage.all import *
>>> from sage.matrix.strassen import int_range
>>> int_range(Integer(2), Integer(4))
[(2, 4)]

Sage Live

from sage.matrix.strassen import int_range
int_range(2, 4)

Default:

Sage

sage: int_range()
[]

Python

>>> from sage.all import *
>>> int_range()
[]

Sage Live

int_range()

From a list of integers:

Sage

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)]

Python

>>> from sage.all import *
>>> int_range([Integer(1),Integer(2),Integer(3),Integer(4)])
[(1, 4)]
>>> int_range([Integer(1),Integer(2),Integer(3),Integer(4),Integer(6),Integer(7),Integer(8)])
[(1, 4), (6, 3)]
>>> int_range([Integer(1),Integer(2),Integer(3),Integer(4),Integer(100),Integer(101),Integer(102)])
[(1, 4), (100, 3)]
>>> int_range([Integer(1),Integer(1000),Integer(2),Integer(101),Integer(3),Integer(4),Integer(100),Integer(102)])
[(1, 4), (100, 3), (1000, 1)]

Sage Live

int_range([1,2,3,4])
int_range([1,2,3,4,6,7,8])
int_range([1,2,3,4,100,101,102])
int_range([1,1000,2,101,3,4,100,102])

Repetitions are not considered:

Sage

sage: int_range([1,2,3])
[(1, 3)]
sage: int_range([1,1,1,1,2,2,2,3])
[(1, 3)]

Python

>>> from sage.all import *
>>> int_range([Integer(1),Integer(2),Integer(3)])
[(1, 3)]
>>> int_range([Integer(1),Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(2),Integer(3)])
[(1, 3)]

Sage Live

int_range([1,2,3])
int_range([1,1,1,1,2,2,2,3])

AUTHORS:

Robert Bradshaw

intervals()[source]¶

Return the list of intervals.

OUTPUT: list of pairs of integers

EXAMPLES:

Sage

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())
<... 'list'>

Python

>>> from sage.all import *
>>> from sage.matrix.strassen import int_range
>>> I = int_range([Integer(4),Integer(5),Integer(6),Integer(20),Integer(21),Integer(22),Integer(23)])
>>> I.intervals()
[(4, 3), (20, 4)]
>>> type(I.intervals())
<... 'list'>

Sage Live

from sage.matrix.strassen import int_range
I = int_range([4,5,6,20,21,22,23])
I.intervals()
type(I.intervals())

to_list()[source]¶

Return the (sorted) list of integers represented by this object.

OUTPUT: list of integers

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> from sage.matrix.strassen import int_range
>>> I = int_range([Integer(6),Integer(20),Integer(21),Integer(4),Integer(5),Integer(22),Integer(23)])
>>> I.to_list()
[4, 5, 6, 20, 21, 22, 23]

Sage Live

from sage.matrix.strassen import int_range
I = int_range([6,20,21,4,5,22,23])
I.to_list()

Sage

sage: I = int_range(34, 9)
sage: I.to_list()
[34, 35, 36, 37, 38, 39, 40, 41, 42]

Python

>>> from sage.all import *
>>> I = int_range(Integer(34), Integer(9))
>>> I.to_list()
[34, 35, 36, 37, 38, 39, 40, 41, 42]

Sage Live

I = int_range(34, 9)
I.to_list()

Python

>>> from sage.all import *
>>> I = int_range(Integer(34), Integer(9))
>>> I.to_list()
[34, 35, 36, 37, 38, 39, 40, 41, 42]

Sage Live

I = int_range(34, 9)
I.to_list()

Repetitions are not considered:

Sage

sage: I = int_range([1,1,1,1,2,2,2,3])
sage: I.to_list()
[1, 2, 3]

Python

>>> from sage.all import *
>>> I = int_range([Integer(1),Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(2),Integer(3)])
>>> I.to_list()
[1, 2, 3]

Sage Live

I = int_range([1,1,1,1,2,2,2,3])
I.to_list()

sage.matrix.strassen.strassen_echelon(A, cutoff)[source]¶

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = matrix(QQ, Integer(7), [Integer(5), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(3), Integer(1), Integer(0), -Integer(1), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(1), Integer(2), -Integer(1), Integer(1), Integer(0), -Integer(1), Integer(0), Integer(1), Integer(3), -Integer(1), Integer(1), Integer(0), Integer(0), -Integer(2), Integer(0), Integer(2), Integer(0), Integer(1), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(1), Integer(0), Integer(1)])
>>> B = A.__copy__(); B._echelon_strassen(Integer(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]
>>> C = A.__copy__(); C._echelon_strassen(Integer(2)); C == B
True
>>> C = A.__copy__(); C._echelon_strassen(Integer(4)); C == B
True

Sage Live

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])
B = A.__copy__(); B._echelon_strassen(1); B
C = A.__copy__(); C._echelon_strassen(2); C == B
C = A.__copy__(); C._echelon_strassen(4); C == B

Sage

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

Python

>>> from sage.all import *
>>> n = Integer(32); A = matrix(Integers(Integer(389)),n,range(n**Integer(2)))
>>> B = A.__copy__(); B._echelon_in_place_classical()
>>> C = A.__copy__(); C._echelon_strassen(Integer(2))
>>> B == C
True

Sage Live

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

Python

>>> from sage.all import *
>>> n = Integer(32); A = matrix(Integers(Integer(389)),n,range(n**Integer(2)))
>>> B = A.__copy__(); B._echelon_in_place_classical()
>>> C = A.__copy__(); C._echelon_strassen(Integer(2))
>>> B == C
True

Sage Live

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

AUTHORS:

Robert Bradshaw

sage.matrix.strassen.strassen_window_multiply(C, A, B, cutoff)[source]¶

Multiply 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

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

Python

>>> from sage.all import *
>>> A = MatrixSpace(Integers(Integer(2)**Integer(65)), Integer(64), Integer(83)).random_element()
>>> B = MatrixSpace(Integers(Integer(2)**Integer(65)), Integer(83), Integer(101)).random_element()
>>> A._multiply_classical(B) == A._multiply_strassen(B, Integer(3)) #indirect doctest
True

Sage Live

A = MatrixSpace(Integers(2^65), 64, 83).random_element()
B = MatrixSpace(Integers(2^65), 83, 101).random_element()
A._multiply_classical(B) == A._multiply_strassen(B, 3) #indirect doctest

AUTHORS:

David Harvey
Simon King (2011-07): Improve memory efficiency; Issue #11610

sage.matrix.strassen.test(n, m, R, c=2)[source]¶

Test code for the Strassen algorithm.

INPUT:

n – integer
m – integer
R – ring
c – integer (default: 2)

EXAMPLES:

Sage

sage: from sage.matrix.strassen import test
sage: for n in range(5):
....:     print("{} {}".format(n, test(2*n,n,Frac(QQ['x']),2)))
0 True
1 True
2 True
3 True
4 True

Python

>>> from sage.all import *
>>> from sage.matrix.strassen import test
>>> for n in range(Integer(5)):
...     print("{} {}".format(n, test(Integer(2)*n,n,Frac(QQ['x']),Integer(2))))
0 True
1 True
2 True
3 True
4 True

Sage Live

from sage.matrix.strassen import test
for n in range(5):
    print("{} {}".format(n, test(2*n,n,Frac(QQ['x']),2)))