Package sage :: Package linalg :: Module dense_matrix_pyx :: Class Matrix_rational
[show private | hide private]
[frames | no frames]

Type Matrix_rational

object --+
         |
        Matrix_rational


Matrix over the rational numbers.
Method Summary
  __init__(...)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
  __cmp__(x, y)
x.__cmp__(y) <==> cmp(x,y)
  __delitem__(x, y)
x.__delitem__(y) <==> del x[y]
  __getitem__(x, y)
x.__getitem__(y) <==> x[y]
  __mul__(x, y)
x.__mul__(y) <==> x*y
  __new__(T, S, ...)
T.__new__(S, ...) -> a new object with type S, a subtype of T
  __repr__(x)
x.__repr__() <==> repr(x)
  __rmul__(x, y)
x.__rmul__(y) <==> y*x
  __setitem__(x, i, y)
x.__setitem__(i, y) <==> x[i]=y
  charpoly(...)
  clear_denom(...)
Replace self by n*self, where n is the least common multiple of the denominators of all entries of self.
  clear_denom_copy(...)
Returns self if the denominator is 1, or n*self, where n is the denominator of self.
  copy(...)
  decompose(...)
  denom(...)
  echelon(...)
echelon(self, alg="modular", height_guess=None):
  echelon_gauss_in_place(...)
Changes self into echelon form.
  echelon_modular(...)
echelon_modular(self, height_guess=None): Returns echelon form of self, without modifying self.
  height(...)
  hessenberg_form(...)
  list(...)
  matrix_modint(...)
  number_nonzero(...)
  pivots(...)
Return the pivots found during the last echelon operation on self.
  rank(...)
Return the rank found during the last echelon operation on self.
  scalar_multiple(...)
    Inherited from object
  __delattr__(...)
x.__delattr__('name') <==> del x.name
  __getattribute__(...)
x.__getattribute__('name') <==> x.name
  __hash__(x)
x.__hash__() <==> hash(x)
  __reduce__(...)
helper for pickle
  __reduce_ex__(...)
helper for pickle
  __setattr__(...)
x.__setattr__('name', value) <==> x.name = value
  __str__(x)
x.__str__() <==> str(x)

Class Variable Summary
PyCObject __pyx_vtable__ = <PyCObject object at 0xb7ca97b8>

Method Details

__init__(...)
(Constructor)

x.__init__(...) initializes x; see x.__class__.__doc__ for signature
Overrides:
__builtin__.object.__init__

__cmp__(x, y)
(Comparison operator)

x.__cmp__(y) <==> cmp(x,y)
Returns:
cmp(x,y)

__delitem__(x, y)
(Index deletion operator)

x.__delitem__(y) <==> del x[y]
Returns:
del x[y]

__getitem__(x, y)
(Indexing operator)

x.__getitem__(y) <==> x[y]
Returns:
x[y]

__mul__(x, y)

x.__mul__(y) <==> x*y
Returns:
x*y

__new__(T, S, ...)

T.__new__(S, ...) -> a new object with type S, a subtype of T
Returns:
a new object with type S, a subtype of T
Overrides:
__builtin__.object.__new__

__repr__(x)
(Representation operator)

x.__repr__() <==> repr(x)
Returns:
repr(x)
Overrides:
__builtin__.object.__repr__

__rmul__(x, y)

x.__rmul__(y) <==> y*x
Returns:
y*x

__setitem__(x, i, y)
(Index assignment operator)

x.__setitem__(i, y) <==> x[i]=y
Returns:
x[i]=y

clear_denom(...)

Replace self by n*self, where n is the least common multiple of the denominators of all entries of self.

clear_denom_copy(...)

Returns self if the denominator is 1, or n*self, where n is the denominator of self.

echelon(...)

echelon(self, alg="modular", height_guess=None):

Returns echelon form of self, without modifying self.

echelon_gauss_in_place(...)

Changes self into echelon form.

echelon_modular(...)

echelon_modular(self, height_guess=None):

Returns echelon form of self, without modifying self.  Uses a
multi-modular method.

ALGORITHM:
The following is a modular algorithm for computing the echelon
form.  Define the height of a matrix to be the max of the
absolute values of the entries.

Input: Matrix A with n columns (this).

0. Rescale input matrix A to have integer entries.  This does
   not change echelon form and makes reduction modulo many
   primes significantly easier if there were denominators.
   Henceforth we assume A has integer entries. 
   
1. Let c be a guess for the height of the echelon form.  E.g.,
   c=1000, since matrix is sparse and application is modular
   symbols.

2. Let M = n * c * H(A) + 1,
   where n is the number of columns of A.

3. List primes p_1, p_2, ..., such that the product of
   the p_i is at least M.

4. Try to compute the rational reconstruction CRT echelon form
   of A mod the product of the p_i.  Throw away those A mod p_i
   whose pivot sequence is not >= all other pivot sequences of
   A mod p_j.
   If rational reconstruction fails, compute 1 more echelon
   forms mod the next prime, and attempt again.  Let E be this
   matrix.

5. Compute the denominator d of E.
   Try to prove that result is correct by checking that
   
         H(d*E) < (prod of reduction primes)/(ncols*H(A)),

   where H denotes the height.   If this fails, do step 4 with
   a few more primes.

   (TODO: Possible idea for optimization: When doing the rational_recon lift,
    keep track of the lcm d of denominators found so far, and given
                     a (mod m)
    first check to see if a*d lifts to an integer with abs <= m/2.
    If so, no nded to do rational recon.  This should be the case
    for most a after a while, and should save substantial time!!!!)

pivots(...)

Return the pivots found during the last echelon operation on self. Of course if self is changed, and the echelon form of self is not recomputed, then the pivots could be incorrect.

rank(...)

Return the rank found during the last echelon operation on self. Of course if self is changed, and the echelon form of self is not recomputed, then the rank could be incorrect.

Class Variable Details

__pyx_vtable__

Type:
PyCObject
Value:
<PyCObject object at 0xb7ca97b8>                                       

Generated by Epydoc 2.1 on Wed May 4 18:06:57 2005 http://epydoc.sf.net