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