|
The following functions and procedures enable the user to access or
set individual entries of sparse matrices.
Given a sparse matrix A over a ring R having m rows and n columns,
and an integer i such that 1 ≤i ≤m,
return the i-th row of A, as a dense vector of length n
(lying in Rn).
Given a sparse matrix A over a ring R having m rows and n columns,
integers i and j such that 1 ≤i ≤m and 1 ≤j ≤n,
return the (i, j)-th entry of A, as an element of the ring R.
Given a sparse matrix A over a ring R having m rows and n columns,
integers i and j such that 1 ≤i ≤m and 1 ≤j ≤n,
and a ring element x coercible into R, modify the (i, j)-th entry
of A to be x. Here i and j must be within the ranges given
by the current dimensions of A; see SetEntry below for a
procedure to automatically extend A if necessary.
SetEntry(~A, i, j, x) : MtrxSprs, RngIntElt, RngIntElt, RngElt ->
(Procedure.)
Given a sparse matrix A over a ring R, integers i, j≥1,
and a ring element x coercible into R, modify the (i, j)-th entry
of A to be x. The entry specified by i and j is allowed to
be beyond the current dimensions of A; if so, A is automatically
extended to have at least i rows and j columns.
This procedure will be commonly used in situations where the final
size of the matrix is not known as an algorithm proceeds
(e.g., in index-calculus methods). One can create the 0 x 0
sparse matrix over Z, say, and then call SetEntry to
build up the matrix dynamically.
See the example H28E3 below, which uses this technique.
Note that extending the dimensions of A with a very large i or j
will not in itself consume much memory, but if A then becomes dense
or is passed to some algorithm, then the memory needed may of course be
proportional to the dimensions of A.
This example demonstrates simple ways of accessing the entries of sparse
matrices.
> A := SparseMatrix(2, 3, [<1,2,3>, <2,3,-1>]);
> A;
Sparse matrix with 2 rows and 3 columns over Integer Ring
> Matrix(A);
[ 0 3 0]
[ 0 0 -1]
> A[1];
(0 3 0)
> A[1, 3]:=5;
> A[1];
(0 3 5)
We next extend A using the procedure SetEntry.
> SetEntry(~A, 1, 5, -7);
> A;
Sparse matrix with 2 rows and 5 columns over Integer Ring
> Matrix(A);
[ 0 3 5 0 -7]
[ 0 0 -1 0 0]
A common situation is to start with the empty 0 x 0 matrix
over Z and then to extend it dynamically.
> A := SparseMatrix();
> A;
Sparse matrix with 0 rows and 0 columns over Integer Ring
> SetEntry(~A, 1, 4, -2);
> A;
Sparse matrix with 1 row and 4 columns over Integer Ring
> SetEntry(~A, 2, 3, 8);
> A;
Sparse matrix with 2 rows and 4 columns over Integer Ring
> Matrix(A);
[ 0 0 0 -2]
[ 0 0 8 0]
> SetEntry(~A, 200, 319, 1);
> SetEntry(~A, 200, 3876, 1);
> A;
Sparse matrix with 200 rows and 3876 columns over Integer Ring
> Nrows(A);
200
> Ncols(A);
3876
> NNZEntries(A);
4
> Density(A);
0.000005159958720330237358101135190
> Support(A, 200);
[ 319, 3876 ]
The following functions enable the extraction of certain rows, columns or
general submatrices, or the replacement of a block by another sparse matrix.
ExtractBlock(A, i, j, p, q) : MtrxSprs, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> MtrxSprs
Given an m x n sparse matrix A and integers i, j, p and q such
that 1≤i ≤i + p ≤m + 1 and 1 ≤j ≤j + q ≤n + 1,
return the p x q submatrix of A rooted at (i, j). Either
or both of p and q may be zero, while i may be m + 1 if p is zero
and j may be n + 1 if q is zero.
ExtractBlockRange(A, i, j, r, s) : MtrxSprs, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> MtrxSprs
Given an m x n sparse matrix A and integers i, j, r and s such
that 1≤i, i - 1 ≤r ≤m, 1 ≤j, and j - 1 ≤s ≤n,
return the r - i + 1 x s - j + 1 submatrix of A rooted at the (i, j)-th
entry and extending to the (r, s)-th entry, inclusive.
r may equal i - 1 or s may equal j - 1, in which case a sparse matrix with
zero rows or zero columns, respectively, will be returned.
Given an m x n sparse matrix A and integer sequences I and J,
return the submatrix of A given by the row indices in I and the
column indices in J.
InsertBlock(~A, B, i, j) : MtrxSprs, MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs
Given an m x n sparse matrix A over a ring R,
a p x q sparse matrix B over R, and integers i and j such
that 1≤i ≤i + p ≤m + 1 and 1 ≤j ≤j + q ≤n + 1,
insert B at position (i, j) in A.
In the functional version (A is a value argument), this function returns
the new sparse matrix and leaves A untouched, while in the procedural
version (~A is a reference argument), A is modified
in place so that the p x q submatrix of A rooted
at (i, j) is now equal to B.
Given an m x n sparse matrix A and integers i and k such
that 1 ≤i ≤i + k ≤m + 1, return the k x n submatrix of
X consisting of rows [i ... i + k - 1] inclusive. The integer
k may be zero and i may also be m + 1 if k is zero, but
the result will always have n columns.
Given an m x n sparse matrix A and an integer i such
that 0 ≤i ≤m, return the i x n submatrix of
X consisting of the first i rows. The integer
i may be 0, but the result will always have n columns.
Given an m x n sparse matrix A and integers i and j such
that 1 ≤i and i - 1 ≤j ≤m, return the j - i + 1 x n submatrix
of X consisting of rows [i ... j] inclusive. The integer
j may equal i - 1, in which case a sparse matrix with zero rows and n
columns will be returned.
Given an m x n sparse matrix A and integers i and k such
that 1 ≤i ≤i + k ≤n + 1, return the m x k submatrix of
X consisting of columns [i ... i + k - 1] inclusive. The integer
k may be zero and i may also be n + 1 if k is zero, but
the result will always have m rows.
Given an m x n sparse matrix A and an integer i such
that 0 ≤i ≤n, return the m x i submatrix of
X consisting of the first i columns. The integer
i may be 0, but the result will always have m rows.
Given an m x n sparse matrix A and integers i and j such
that 1 ≤i and i - 1 ≤j ≤n, return the m x j - i + 1 submatrix
of X consisting of columns [i ... j] inclusive. The integer
j may equal i - 1, in which case a sparse matrix with zero columns and n
rows will be returned.
The following functions and procedures provide elementary row or
column operations on sparse matrices. For each operation, there is a
corresponding function which creates a new sparse matrix for the result
(leaving the input sparse matrix unchanged), and a corresponding procedure
which modifies the input sparse matrix in place.
SwapRows(~A, i, j) : MtrxSprs, RngIntElt, RngIntElt ->
Given an m x n sparse matrix A and integers i and j such that 1
≤i≤m and 1 ≤j ≤m, swap the i-th and j-th rows of
A.
SwapColumns(~A, i, j) : MtrxSprs, RngIntElt, RngIntElt ->
Given an m x n sparse matrix A and integers i and j such that 1
≤i≤n and 1 ≤j ≤n, swap the i-th and j-th columns of
A.
ReverseRows(~A) : MtrxSprs ->
Given a sparse matrix A, reverse all the rows of A.
ReverseColumns(~A) : MtrxSprs ->
Given a sparse matrix A, reverse all the columns of A.
AddRow(~A, c, i, j) : MtrxSprs, RngElt, RngIntElt, RngIntElt ->
Given an m x n sparse matrix A over a ring R, a ring element c
coercible into R, and integers i and j such that 1
≤i≤m and 1 ≤j ≤m, add c times row i of A
to row j of A.
AddColumn(~A, c, i, j) : MtrxSprs, RngElt, RngIntElt, RngIntElt ->
Given an m x n sparse matrix A over a ring R, a ring element c
coercible into R, and integers i and j such that 1
≤i≤n and 1 ≤j ≤n, add c times column i of A
to column j.
MultiplyRow(~A, c, i) : MtrxSprs, RngElt, RngIntElt ->
Given an m x n sparse matrix A over a ring R, a ring element c
coercible into R, and an integer i such that 1
≤i≤m, multiply row i of A by c (on the left).
MultiplyColumn(~A, c, i) : MtrxSprs, RngElt, RngIntElt ->
Given an m x n sparse matrix A over a ring R, a ring element c
coercible into R, and an integer i such that 1
≤i≤n, multiply column i of A by c (on the left).
RemoveRow(~A, i) : MtrxSprs, RngIntElt ->
Given an m x n sparse matrix A and an integer i such that 1 ≤i≤m,
remove row i from A (leaving an (m - 1) x n sparse matrix).
RemoveColumn(~A, j) : MtrxSprs, RngIntElt ->
Given an m x n sparse matrix A and an integer j such that 1 ≤j≤n,
remove column j from A (leaving an m x (n - 1) sparse matrix).
RemoveRowColumn(~A, i, j) : MtrxSprs, RngIntElt ->
Given an m x n sparse matrix A and integers i and j such that
1 ≤i≤m and 1 ≤j≤n, remove row i and column j from
A (leaving an (m - 1) x (n - 1) sparse matrix).
RemoveZeroRows(~A) : MtrxSprs ->
Given a sparse matrix A, remove all the zero rows of A.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|