Coverage for local/lib/python2.7/site-packages/sage/matroids/lean_matrix.pyx : 68%

# cython: profile=True 

""" 

Lean matrices 

Internal data structures for the ``LinearMatroid`` class and some subclasses. 

Note that many of the methods are ``cdef``, and therefore only available from 

Cython code. 

.. warning:: 

Intended for internal use by the ``LinearMatroid`` classes only. End users 

should work with Sage matrices instead. Methods that are used outside 

lean_matrix.pyx and have no equivalent in Sage's ``Matrix`` have been 

flagged in the code, as well as where they are used, by ``# Not a Sage 

matrix operation`` or ``# Deprecated Sage matrix operation``. 

AUTHORS: 

- Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version 

""" 

#***************************************************************************** 

# Copyright (C) 2013 Rudi Pendavingh <rudi.pendavingh@gmail.com> 

# Copyright (C) 2013 Stefan van Zwam <stefanvanzwam@gmail.com> 

# 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# as published by the Free Software Foundation; either version 2 of 

# the License, or (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from __future__ import absolute_import 

include 'sage/data_structures/bitset.pxi' 

from libc.string cimport memcpy, memset 

from cpython.object cimport Py_EQ, Py_NE 

from cysignals.memory cimport sig_malloc, sig_realloc, sig_free 

from sage.matrix.matrix2 cimport Matrix 

from sage.rings.all import ZZ, FiniteField, GF 

from sage.rings.integer cimport Integer 

import sage.matrix.constructor 

cdef class LeanMatrix: 

""" 

Lean matrices 

Sage's matrix classes are powerful, versatile, and often very fast. However, their performance with regard to pivoting 

(pretty much the only task performed on them within the context of matroids) leaves something to be desired. The LeanMatrix 

classes provide the LinearMatroid classes with a custom, light-weight data structure to store and manipulate matrices. 

This is the abstract base class. Most methods are not implemented; this is only to fix the interface. 

.. NOTE:: 

This class is intended for internal use by the LinearMatroid class only. Hence it does not derive from ``SageObject``. 

If ``A`` is a LeanMatrix instance, and you need access from other parts of Sage, use ``Matrix(A)`` instead. 

EXAMPLES:: 

sage: M = Matroid(ring=GF(5), matrix=[[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]]) # indirect doctest 

sage: M.is_isomorphic(matroids.Uniform(2, 5)) 

True 

""" 

def __init__(self, long m, long n, M=None): 

""" 

Initialize a lean matrix; see class documentation for more info. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import LeanMatrix 

sage: A = LeanMatrix(3, 4) 

sage: A.ncols() 

4 

""" 

self._nrows = m 

self._ncols = n 

def __repr__(self): 

""" 

Return a string representation. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import LeanMatrix 

sage: A = LeanMatrix(3, 4) 

sage: repr(A) 

'LeanMatrix instance with 3 rows and 4 columns' 

""" 

return "LeanMatrix instance with " + str(self._nrows) + " rows and " + str(self._ncols) + " columns" 

def _matrix_(self): 

""" 

Return a matrix version. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import GenericMatrix 

sage: A = Matrix(GF(5), [[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]]) 

sage: A == GenericMatrix(2, 5, A)._matrix_() 

True 

""" 

cdef long r, c 

M = sage.matrix.constructor.Matrix(self.base_ring(), self._nrows, self._ncols) 

for r from 0 <= r < self._nrows: 

for c from 0 <= c < self._ncols: 

M[r, c] = self.get_unsafe(r, c) 

return M 

cdef LeanMatrix copy(self): # Deprecated Sage matrix operation 

""" 

Make a copy of ``self``. 

""" 

cdef LeanMatrix A = type(self)(self.nrows(), self.ncols(), self) 

return A 

cdef int resize(self, long k) except -1: # Not a Sage matrix operation 

""" 

Change number of rows of ``self`` to ``k``. Preserves data. 

""" 

raise NotImplementedError 

cdef LeanMatrix stack(self, LeanMatrix M): 

""" 

Stack ``self`` on top of ``M``. Assumes ``self`` and ``M`` are of same 

type, and compatible dimensions. 

""" 

cdef LeanMatrix A 

cdef long i, j 

cdef long sr = self.nrows() 

A = type(self)(sr + M.nrows(), self.ncols()) 

for i from 0 <= i < sr: 

for j from 0 <= j < self.ncols(): 

A.set_unsafe(i, j, self.get_unsafe(i, j)) 

for i from 0 <= i < M.nrows(): 

for j from 0 <= j < M.ncols(): 

A.set_unsafe(i + sr, j, M.get_unsafe(i, j)) 

return A 

cdef LeanMatrix augment(self, LeanMatrix M): 

""" 

Concatenates ``self`` with ``M``, placing ``M`` to the right of 

``self``. Assumes ``self`` and ``M`` are of same type, and compatible 

dimensions. 

""" 

cdef LeanMatrix A 

cdef long i, j 

cdef long sc = self.ncols() 

A = type(self)(self.nrows(), sc + M.ncols()) 

for i from 0 <= i < self.nrows(): 

for j from 0 <= j < sc: 

A.set_unsafe(i, j, self.get_unsafe(i, j)) 

for j from 0 <= j < M.ncols(): 

A.set_unsafe(i, j + sc, M.get_unsafe(i, j)) 

return A 

cdef LeanMatrix prepend_identity(self): # Not a Sage matrix operation 

""" 

Return the matrix obtained by prepending an identity matrix. Special 

case of ``augment``. 

""" 

cdef long i, j 

cdef LeanMatrix A = type(self)(self.nrows(), self.ncols() + self.nrows()) 

for i from 0 <= i < self.nrows(): 

A.set_unsafe(i, i, self.base_ring()(1)) 

for j from 0 <= j < self.ncols(): 

A.set_unsafe(i, self.nrows() + j, self.get_unsafe(i, j)) 

return A 

cpdef long ncols(self) except -1: 

""" 

Return the number of columns. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import LeanMatrix 

sage: A = LeanMatrix(3, 4) 

sage: A.ncols() 

4 

""" 

return self._ncols 

cpdef long nrows(self) except -1: 

""" 

Return the number of rows. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import LeanMatrix 

sage: A = LeanMatrix(3, 4) 

sage: A.nrows() 

3 

""" 

return self._nrows 

cpdef base_ring(self): 

""" 

Return the base ring. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import LeanMatrix 

sage: A = LeanMatrix(3, 4) 

sage: A.base_ring() 

Traceback (most recent call last): 

... 

NotImplementedError: subclasses need to implement this. 

""" 

raise NotImplementedError("subclasses need to implement this.") 

cpdef characteristic(self): 

""" 

Return the characteristic of ``self.base_ring()``. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import GenericMatrix 

sage: A = GenericMatrix(3, 4, ring=GF(5)) 

sage: A.characteristic() 

5 

""" 

return self.base_ring().characteristic() 

cdef get_unsafe(self, long r, long c): 

""" 

Return the value in row ``r``, column ``c``. 

""" 

raise NotImplementedError 

cdef int set_unsafe(self, long r, long c, x) except -1: 

""" 

Set the value in row ``r``, column ``c`` to ``x``. 

""" 

raise NotImplementedError 

cdef bint is_nonzero(self, long r, long c) except -2: # Not a Sage matrix operation 

""" 

Check if value in row ``r``, column ``c`` equals ``0``. 

""" 

return self.get_unsafe(r, c) != 0 

cdef int add_multiple_of_row_c(self, long x, long y, s, bint col_start) except -1: 

""" 

Add ``s`` times row ``y`` to row ``x``. Argument ``col_start`` is 

ignored. 

""" 

cdef long i 

if s is None: 

for i from 0 <= i < self._ncols: 

self.set_unsafe(x, i, self.get_unsafe(x, i) + self.get_unsafe(y, i)) 

else: 

for i from 0 <= i < self._ncols: 

self.set_unsafe(x, i, self.get_unsafe(x, i) + s * self.get_unsafe(y, i)) 

return 0 

cdef int swap_rows_c(self, long x, long y) except -1: 

""" 

Swap rows ``x`` and ``y``. 

""" 

cdef long i 

for i from 0 <= i < self._ncols: 

tmp = self.get_unsafe(x, i) 

self.set_unsafe(x, i, self.get_unsafe(y, i)) 

self.set_unsafe(y, i, tmp) 

return 0 

cdef int rescale_row_c(self, long x, s, bint col_start) except -1: 

""" 

Scale row ``x`` by ``s``. Argument ``col_start`` is for Sage 

compatibility, and is ignored. 

""" 

cdef long i 

for i from 0 <= i < self._ncols: 

self.set_unsafe(x, i, s * self.get_unsafe(x, i)) 

return 0 

cdef int rescale_column_c(self, long y, s, bint start_row) except -1: 

""" 

Scale column ``y`` by ``s``. Argument ``start_row`` is for Sage 

compatibility, and ignored. 

""" 

cdef long j 

for j from 0 <= j < self._nrows: 

self.set_unsafe(j, y, self.get_unsafe(j, y) * s) 

return 0 

cdef int pivot(self, long x, long y) except -1: # Not a Sage matrix operation 

""" 

Row-reduce to make column ``y`` have a ``1`` in row ``x`` and zeroes 

elsewhere. 

Assumption (not checked): the entry in row ``x``, column ``y`` is 

nonzero to start with. 

.. NOTE:: 

This is different from what matroid theorists tend to call a 

pivot, as it does not involve a column exchange! 

""" 

cdef long i, j 

self.rescale_row_c(x, self.get_unsafe(x, y) ** (-1), 0) 

for i from 0 <= i < self._nrows: 

s = self.get_unsafe(i, y) 

if s and i != x: 

self.add_multiple_of_row_c(i, x, -s, 0) 

return 0 

cdef list gauss_jordan_reduce(self, columns): # Not a Sage matrix operation 

""" 

Row-reduce so the lexicographically first basis indexes an identity 

submatrix. 

""" 

cdef long r = 0 

cdef list P = [] 

cdef long c, p, row 

cdef bint is_pivot 

for c in columns: 

is_pivot = False 

for row from r <= row < self._nrows: 

if self.is_nonzero(row, c): 

is_pivot = True 

p = row 

break 

if is_pivot: 

self.swap_rows_c(p, r) 

self.pivot(r, c) 

P.append(c) 

r += 1 

if r == self._nrows: 

break 

return P 

cdef list nonzero_positions_in_row(self, long r): 

""" 

Get coordinates of nonzero entries of row ``r``. 

""" 

return [i for i in xrange(self._ncols) if self.is_nonzero(r, i)] 

cdef LeanMatrix transpose(self): 

""" 

Return the transpose of the matrix. 

""" 

cdef LeanMatrix A = type(self)(self.ncols(), self.nrows()) 

cdef long i, j 

for i from 0 <= i < self.nrows(): 

for j from 0 <= j < self.ncols(): 

A.set_unsafe(j, i, self.get_unsafe(i, j)) 

return A 

cdef LeanMatrix _matrix_times_matrix_(self, LeanMatrix other): 

""" 

Multiply two matrices. Assumes ``self`` and ``M`` are of same type, 

and compatible dimensions. 

""" 

cdef LeanMatrix A = type(self)(self.nrows(), other.ncols()) 

cdef i, j, k 

for i from 0 <= i < self.nrows(): 

for j from 0 <= j < other.ncols(): 

for k from 0 <= k < self.ncols(): 

A.set_unsafe(i, j, self.get_unsafe(i, k) * other.get_unsafe(k, j)) 

return A 

cdef LeanMatrix matrix_from_rows_and_columns(self, rows, columns): 

""" 

Return submatrix indexed by indicated rows and columns. 

""" 

cdef long r, c 

cdef LeanMatrix A = type(self)(len(rows), len(columns), ring=self.base_ring()) 

for r from 0 <= r < len(rows): 

for c from 0 <= c < len(columns): 

A.set_unsafe(r, c, self.get_unsafe(rows[r], columns[c])) 

return A 

def __mul__(left, right): 

""" 

Multiply two matrices, or multiply a matrix with a constant from the 

base ring. 

Only works if both matrices are of the same type, or if the constant 

is the first operand and can be coerced into the base ring. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import * 

sage: A = GenericMatrix(2, 2, Matrix(GF(2), [[1, 0], [1, 1]])) 

sage: B = GenericMatrix(3, 2, Matrix(GF(2), [[1, 0], [1, 0], [1, 0]])) 

sage: B * A 

LeanMatrix instance with 3 rows and 2 columns over Finite Field of size 2 

""" 

cdef long i 

cdef LeanMatrix A 

if isinstance(left, LeanMatrix): 

if type(left) == type(right): 

return (<LeanMatrix>left)._matrix_times_matrix_(right) 

else: 

return NotImplemented 

if not left in (<LeanMatrix>right).base_ring(): 

try: 

left = (<LeanMatrix>right).base_ring()(left) 

except (TypeError, NotImplemented, ValueError): 

return NotImplemented 

A = (<LeanMatrix>right).copy() 

for i from 0 <= i < A.nrows(): 

A.rescale_row_c(i, left, 0) 

return A 

def __neg__(self): 

""" 

Return a matrix ``B`` such that ``self + B`` is the all-zero matrix. 

Note that the `` + `` operator is currently not supported. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import * 

sage: A = GenericMatrix(2, 2, Matrix(GF(3), [[1, 0], [0, 1]])) 

sage: C = -A 

sage: -C == A 

True 

""" 

cdef long i 

cdef LeanMatrix A = self.copy() 

x = self.base_ring()(-1) 

for i from 0 <= i < A.nrows(): 

A.rescale_row_c(i, x, 0) 

return A 

def __richcmp__(left, right, op): 

""" 

Compare two matrices. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import * 

sage: A = GenericMatrix(2, 2, Matrix(GF(2), [[1, 0], [0, 1]])) 

sage: B = GenericMatrix(2, 2, Matrix(GF(2), [[1, 0], [0, 1]])) 

sage: C = GenericMatrix(2, 2, Matrix(GF(2), [[1, 1], [0, 1]])) 

sage: D = BinaryMatrix(2, 2, Matrix(GF(2), [[1, 1], [0, 1]])) 

sage: E = GenericMatrix(2, 3, Matrix(GF(2), [[1, 0, 0], [0, 1, 0]])) 

sage: A == B # indirect doctest 

True 

sage: A != C # indirect doctest 

True 

sage: A == D # indirect doctest 

False 

sage: E == A 

False 

""" 

cdef long i, j 

if op not in [Py_EQ, Py_NE]: 

return NotImplemented 

if not isinstance(left, LeanMatrix) or not isinstance(right, LeanMatrix): 

return NotImplemented 

if type(left) != type(right): 

return NotImplemented 

if op == Py_EQ: 

res = True 

if op == Py_NE: 

res = False 

# res gets inverted if matroids are deemed different. 

if left.nrows() != right.nrows(): 

return not res 

if left.ncols() != right.ncols(): 

return not res 

for i from 0 <= i < left.nrows(): 

for j from 0 <= j < left.ncols(): 

if (<LeanMatrix>left).get_unsafe(i, j) != (<LeanMatrix>right).get_unsafe(i, j): 

return not res 

return res 

# In Cythonized classes, use ``__richcmp__()`` instead of ``__eq__()``, ``__ne__()``. 

# Copying, loading, saving: 

def __copy__(self): 

""" 

Return a copy of ``self``. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import * 

sage: A = GenericMatrix(2, 5, Matrix(GF(5), [[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]])) 

sage: A == copy(A) # indirect doctest 

True 

""" 

return self.copy() 

def __deepcopy__(self, memo={}): 

""" 

Return a deep copy of ``self``. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import * 

sage: A = GenericMatrix(2, 5, Matrix(GF(5), [[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]])) 

sage: A == deepcopy(A) # indirect doctest 

True 

""" 

return self.copy() 

def __reduce__(self): 

""" 

Save the object. 

EXAMPLES:: 

sage: from sage.matroids.lean_matrix import * 

sage: A = LeanMatrix(2, 5) 

sage: A == loads(dumps(A)) # indirect doctest 

Traceback (most recent call last): 

... 

NotImplementedError: subclasses need to implement this. 

""" 

raise NotImplementedError("subclasses need to implement this.") 

cdef shifting_all(self, P_rows, P_cols, Q_rows, Q_cols, int m): 

r""" 

Given a partial matrix `M`. If the submatrix `M` using rows 

`P_rows` columns `P_cols` and submatrix using rows `Q_rows` columns 

`Q_cols` can be extended to a ``m``-separator, then it returns 

`True, E`, where `E` is a ``m``-separator. Otherwise it returns 

`False, None` 

`P_rows` and `Q_rows` must be disjoint subsets of row indices. 

`P_cols` and `Q_cols` must be disjoint subsets of column indices. 

Internal version does not verify the above properties hold.  

INPUT: 

- ``P_rows`` -- list of row indices of the first submatrix 

- ``P_cols`` -- list of column indices of the first submatrix 

- ``Q_rows`` -- list of row indices of the second submatrix 

- ``Q_cols`` -- list of column indices of the second submatrix