Home | Trees | Index | Help |
|
---|
Package sage :: Package linalg :: Module sparse_matrix :: Class Sparse_matrix_rational |
|
object
--+ |SparseMatrix
--+ |Sparse_matrix_generic
--+ | Sparse_matrix_rational
A sparse matrix over the rational numbers. Once you create the matrix you can not change specific entries. However you can compute the echelon form, which uses a sparse multi-modular method. Create with Sparse_matrix_rational(nrows, ncols, entries) INPUT: nrows -- integer, the number of rows ncols -- integer, the number of columns entries-- list of tuples (i,j,x), where 0 <= i < nrows, 0 <= j < ncols, and x is a Python object that has a string representation that can be parsed as a gmp mpq. All the x's are assumed *nonzero*!
Method Summary | |
---|---|
__init__(self,
_,
nrows,
ncols,
entries,
coerce,
sort,
copy)
| |
Replace self by n*self, where n is the least common multiple of the denominators of all entries of self. | |
Return the least common multiple of the denominators of the entries of self. | |
todo | |
Returns echelon form of self, possibly modifying self by rescaling. | |
Returns the height of self, which is the maximum of the absolute values of all numerators and denominators of the elements of self. | |
matrix_modint(self,
n)
| |
The sparcity is a bound on the number of nonzeros per row. | |
entries is a list of triples (i,j,x) and the x must be nonzero. | |
Inherited from Sparse_matrix_generic | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
Returns the sparse submatrix of self composed of the given list of columns. | |
The sparse matrix got by deleted all pivot columns. | |
Returns the sparse submatrix of self composed of the given list of rows. | |
| |
| |
| |
| |
Return the ith row of this matrix as a sparse vector. | |
Return a list of the sparse rows of this matrix. | |
| |
Returns the transpose of self. | |
Inherited from SparseMatrix | |
(Static method) | |
Inherited from object | |
x.__delattr__('name') <==> del x.name | |
x.__getattribute__('name') <==> x.name | |
x.__hash__() <==> hash(x) | |
helper for pickle | |
helper for pickle | |
x.__setattr__('name', value) <==> x.name = value | |
x.__str__() <==> str(x) |
Instance Method Details |
---|
clear_denom(self)Replace self by n*self, where n is the least common multiple of the denominators of all entries of self. |
denom(self)Return the least common multiple of the denominators of the entries of self. |
dense_matrix(self)todo
|
echelon_form(self, height_guess=None)Returns echelon form of self, possibly modifying self by rescaling. Uses a sparse 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 lots of 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. If rational reconstruction fails, compute 1 more echelon forms mod the next prime, and attempt again. Make sure to keep the result of CRT on the primes from before, so we don't have to do that computation 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)*ncols(A)*H(A) < (prod of reduction primes) where H denotes the height. If this fails, do step 4 with a few more primes |
height(self)Returns the height of self, which is the maximum of the absolute values of all numerators and denominators of the elements of self. Since 0 = 0/1 has denominator 1, the height is at least 1. |
randomize(self, sparcity=4, bound=2, bound_denom=2, exact=False)The sparcity is a bound on the number of nonzeros per row. |
set_entries(self, entries, coerce=True, sort=True, copy=True)entries is a list of triples (i,j,x) and the x must be nonzero. This function does *not* check that i and j are in bounds or that the x are all nonzero.
|
Home | Trees | Index | Help |
|
---|
Generated by Epydoc 2.1 on Fri May 20 19:41:04 2005 | http://epydoc.sf.net |