Mercurial > octave-nkf
annotate doc/interpreter/sparse.txi @ 14138:72c96de7a403 stable
maint: update copyright notices for 2012
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Mon, 02 Jan 2012 14:25:41 -0500 |
| parents | 951eacaf9381 |
| children | c3fd61c59e9c f2f5dd09e97d |
| rev | line source |
|---|---|
|
14138
72c96de7a403
maint: update copyright notices for 2012
John W. Eaton <jwe@octave.org>
parents:
14116
diff
changeset
|
1 @c Copyright (C) 2004-2012 David Bateman |
| 7018 | 2 @c |
| 3 @c This file is part of Octave. | |
| 4 @c | |
| 5 @c Octave is free software; you can redistribute it and/or modify it | |
| 6 @c under the terms of the GNU General Public License as published by the | |
| 7 @c Free Software Foundation; either version 3 of the License, or (at | |
| 8 @c your option) any later version. | |
| 9 @c | |
| 10 @c Octave is distributed in the hope that it will be useful, but WITHOUT | |
| 11 @c ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 12 @c FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 13 @c for more details. | |
| 14 @c | |
| 15 @c You should have received a copy of the GNU General Public License | |
| 16 @c along with Octave; see the file COPYING. If not, see | |
| 17 @c <http://www.gnu.org/licenses/>. | |
| 5164 | 18 |
| 5648 | 19 @ifhtml |
| 20 @set htmltex | |
| 21 @end ifhtml | |
| 22 @iftex | |
| 23 @set htmltex | |
| 24 @end iftex | |
| 25 | |
| 5164 | 26 @node Sparse Matrices |
| 27 @chapter Sparse Matrices | |
| 28 | |
| 29 @menu | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
30 * Basics:: Creation and Manipulation of Sparse Matrices |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
31 * Sparse Linear Algebra:: Linear Algebra on Sparse Matrices |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
32 * Iterative Techniques:: Iterative Techniques |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
33 * Real Life Example:: Using Sparse Matrices |
| 5164 | 34 @end menu |
| 35 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
36 @node Basics |
| 5164 | 37 @section The Creation and Manipulation of Sparse Matrices |
| 38 | |
| 39 The size of mathematical problems that can be treated at any particular | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
40 time is generally limited by the available computing resources. Both, |
| 5164 | 41 the speed of the computer and its available memory place limitation on |
| 42 the problem size. | |
| 43 | |
| 5506 | 44 There are many classes of mathematical problems which give rise to |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
45 matrices, where a large number of the elements are zero. In this case |
| 5164 | 46 it makes sense to have a special matrix type to handle this class of |
| 47 problems where only the non-zero elements of the matrix are | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
48 stored. Not only does this reduce the amount of memory to store the |
| 5164 | 49 matrix, but it also means that operations on this type of matrix can |
| 50 take advantage of the a-priori knowledge of the positions of the | |
| 51 non-zero elements to accelerate their calculations. | |
| 52 | |
| 53 A matrix type that stores only the non-zero elements is generally called | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
54 sparse. It is the purpose of this document to discuss the basics of the |
| 5164 | 55 storage and creation of sparse matrices and the fundamental operations |
| 56 on them. | |
| 57 | |
| 58 @menu | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
59 * Storage of Sparse Matrices:: |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
60 * Creating Sparse Matrices:: |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
61 * Information:: |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
62 * Operators and Functions:: |
| 5164 | 63 @end menu |
| 64 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
65 @node Storage of Sparse Matrices |
| 5164 | 66 @subsection Storage of Sparse Matrices |
| 67 | |
| 68 It is not strictly speaking necessary for the user to understand how | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
69 sparse matrices are stored. However, such an understanding will help |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
70 to get an understanding of the size of sparse matrices. Understanding |
| 5164 | 71 the storage technique is also necessary for those users wishing to |
| 72 create their own oct-files. | |
| 73 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
74 There are many different means of storing sparse matrix data. What all |
| 5648 | 75 of the methods have in common is that they attempt to reduce the complexity |
| 5164 | 76 and storage given a-priori knowledge of the particular class of problems |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
77 that will be solved. A good summary of the available techniques for storing |
|
10791
3140cb7a05a1
Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents:
10711
diff
changeset
|
78 sparse matrix is given by Saad @footnote{Y. Saad "SPARSKIT: A basic toolkit |
| 5164 | 79 for sparse matrix computation", 1994, |
| 6620 | 80 @url{http://www-users.cs.umn.edu/~saad/software/SPARSKIT/paper.ps}}. |
| 5164 | 81 With full matrices, knowledge of the point of an element of the matrix |
| 82 within the matrix is implied by its position in the computers memory. | |
| 83 However, this is not the case for sparse matrices, and so the positions | |
| 84 of the non-zero elements of the matrix must equally be stored. | |
| 85 | |
| 86 An obvious way to do this is by storing the elements of the matrix as | |
| 5506 | 87 triplets, with two elements being their position in the array |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
88 (rows and column) and the third being the data itself. This is conceptually |
| 5164 | 89 easy to grasp, but requires more storage than is strictly needed. |
| 90 | |
| 5648 | 91 The storage technique used within Octave is the compressed column |
| 5164 | 92 format. In this format the position of each element in a row and the |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
93 data are stored as previously. However, if we assume that all elements |
| 5164 | 94 in the same column are stored adjacent in the computers memory, then |
| 95 we only need to store information on the number of non-zero elements | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
96 in each column, rather than their positions. Thus assuming that the |
| 5164 | 97 matrix has more non-zero elements than there are columns in the |
| 98 matrix, we win in terms of the amount of memory used. | |
| 99 | |
| 100 In fact, the column index contains one more element than the number of | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
101 columns, with the first element always being zero. The advantage of |
| 7001 | 102 this is a simplification in the code, in that there is no special case |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
103 for the first or last columns. A short example, demonstrating this in |
| 5164 | 104 C is. |
| 105 | |
| 106 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
107 @group |
| 5164 | 108 for (j = 0; j < nc; j++) |
| 109 for (i = cidx (j); i < cidx(j+1); i++) | |
| 5648 | 110 printf ("non-zero element (%i,%i) is %d\n", |
|
10599
d0e0bb2ebebb
Remove tabs in .txi files causing problems with pdf formatting.
Rik <octave@nomad.inbox5.com>
parents:
9906
diff
changeset
|
111 ridx(i), j, data(i)); |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
112 @end group |
| 5164 | 113 @end example |
| 114 | |
| 115 A clear understanding might be had by considering an example of how the | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
116 above applies to an example matrix. Consider the matrix |
| 5164 | 117 |
| 118 @example | |
| 119 @group | |
| 120 1 2 0 0 | |
| 121 0 0 0 3 | |
| 122 0 0 0 4 | |
| 123 @end group | |
| 124 @end example | |
| 125 | |
| 126 The non-zero elements of this matrix are | |
| 127 | |
| 128 @example | |
| 129 @group | |
| 130 (1, 1) @result{} 1 | |
| 131 (1, 2) @result{} 2 | |
| 132 (2, 4) @result{} 3 | |
| 133 (3, 4) @result{} 4 | |
| 134 @end group | |
| 135 @end example | |
| 136 | |
| 137 This will be stored as three vectors @var{cidx}, @var{ridx} and @var{data}, | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
138 representing the column indexing, row indexing and data respectively. The |
| 5164 | 139 contents of these three vectors for the above matrix will be |
| 140 | |
| 141 @example | |
| 142 @group | |
| 5506 | 143 @var{cidx} = [0, 1, 2, 2, 4] |
| 5164 | 144 @var{ridx} = [0, 0, 1, 2] |
| 145 @var{data} = [1, 2, 3, 4] | |
| 146 @end group | |
| 147 @end example | |
| 148 | |
| 149 Note that this is the representation of these elements with the first row | |
| 5648 | 150 and column assumed to start at zero, while in Octave itself the row and |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
151 column indexing starts at one. Thus the number of elements in the |
| 5164 | 152 @var{i}-th column is given by @code{@var{cidx} (@var{i} + 1) - |
| 153 @var{cidx} (@var{i})}. | |
| 154 | |
| 5648 | 155 Although Octave uses a compressed column format, it should be noted |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
156 that compressed row formats are equally possible. However, in the |
| 5648 | 157 context of mixed operations between mixed sparse and dense matrices, |
| 158 it makes sense that the elements of the sparse matrices are in the | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
159 same order as the dense matrices. Octave stores dense matrices in |
| 5648 | 160 column major ordering, and so sparse matrices are equally stored in |
| 161 this manner. | |
| 5164 | 162 |
| 5324 | 163 A further constraint on the sparse matrix storage used by Octave is that |
| 5164 | 164 all elements in the rows are stored in increasing order of their row |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
165 index, which makes certain operations faster. However, it imposes |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
166 the need to sort the elements on the creation of sparse matrices. Having |
| 7001 | 167 disordered elements is potentially an advantage in that it makes operations |
| 5164 | 168 such as concatenating two sparse matrices together easier and faster, however |
| 169 it adds complexity and speed problems elsewhere. | |
| 170 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
171 @node Creating Sparse Matrices |
| 5164 | 172 @subsection Creating Sparse Matrices |
| 173 | |
| 174 There are several means to create sparse matrix. | |
| 175 | |
| 176 @table @asis | |
| 177 @item Returned from a function | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
178 There are many functions that directly return sparse matrices. These include |
|
7515
f3c00dc0912b
Eliminate the rest of the dispatched sparse functions
David Bateman <dbateman@free.fr>
parents:
7505
diff
changeset
|
179 @dfn{speye}, @dfn{sprand}, @dfn{diag}, etc. |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
180 |
| 5164 | 181 @item Constructed from matrices or vectors |
| 182 The function @dfn{sparse} allows a sparse matrix to be constructed from | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
183 three vectors representing the row, column and data. Alternatively, the |
| 5164 | 184 function @dfn{spconvert} uses a three column matrix format to allow easy |
| 185 importation of data from elsewhere. | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
186 |
| 5164 | 187 @item Created and then filled |
| 188 The function @dfn{sparse} or @dfn{spalloc} can be used to create an empty | |
| 189 matrix that is then filled by the user | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
190 |
| 5164 | 191 @item From a user binary program |
| 192 The user can directly create the sparse matrix within an oct-file. | |
| 193 @end table | |
| 194 | |
| 195 There are several basic functions to return specific sparse | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
196 matrices. For example the sparse identity matrix, is a matrix that is |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
197 often needed. It therefore has its own function to create it as |
| 5164 | 198 @code{speye (@var{n})} or @code{speye (@var{r}, @var{c})}, which |
| 199 creates an @var{n}-by-@var{n} or @var{r}-by-@var{c} sparse identity | |
| 200 matrix. | |
| 201 | |
| 202 Another typical sparse matrix that is often needed is a random distribution | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
203 of random elements. The functions @dfn{sprand} and @dfn{sprandn} perform |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
204 this for uniform and normal random distributions of elements. They have exactly |
| 5506 | 205 the same calling convention, where @code{sprand (@var{r}, @var{c}, @var{d})}, |
| 206 creates an @var{r}-by-@var{c} sparse matrix with a density of filled | |
| 5164 | 207 elements of @var{d}. |
| 208 | |
| 7001 | 209 Other functions of interest that directly create sparse matrices, are |
|
7515
f3c00dc0912b
Eliminate the rest of the dispatched sparse functions
David Bateman <dbateman@free.fr>
parents:
7505
diff
changeset
|
210 @dfn{diag} or its generalization @dfn{spdiags}, that can take the |
| 5164 | 211 definition of the diagonals of the matrix and create the sparse matrix |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
212 that corresponds to this. For example, |
| 5164 | 213 |
| 214 @example | |
|
7515
f3c00dc0912b
Eliminate the rest of the dispatched sparse functions
David Bateman <dbateman@free.fr>
parents:
7505
diff
changeset
|
215 s = diag (sparse(randn(1,n)), -1); |
| 5164 | 216 @end example |
| 217 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
218 @noindent |
| 5164 | 219 creates a sparse (@var{n}+1)-by-(@var{n}+1) sparse matrix with a single |
| 220 diagonal defined. | |
| 221 | |
| 6620 | 222 @DOCSTRING(spdiags) |
| 223 | |
| 224 @DOCSTRING(speye) | |
| 225 | |
| 226 @DOCSTRING(spones) | |
| 227 | |
| 228 @DOCSTRING(sprand) | |
| 229 | |
| 230 @DOCSTRING(sprandn) | |
| 231 | |
| 232 @DOCSTRING(sprandsym) | |
| 233 | |
| 5164 | 234 The recommended way for the user to create a sparse matrix, is to create |
| 5648 | 235 two vectors containing the row and column index of the data and a third |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
236 vector of the same size containing the data to be stored. For example, |
| 5164 | 237 |
| 238 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
239 @group |
| 6421 | 240 ri = ci = d = []; |
| 241 for j = 1:c | |
|
13198
0a1774f1a70d
Update example in sparse.txi to use new calling form of randperm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
11593
diff
changeset
|
242 ri = [ri; randperm(r,n)']; |
| 6421 | 243 ci = [ci; j*ones(n,1)]; |
| 244 d = [d; rand(n,1)]; | |
| 245 endfor | |
| 246 s = sparse (ri, ci, d, r, c); | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
247 @end group |
| 5164 | 248 @end example |
| 249 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
250 @noindent |
| 6421 | 251 creates an @var{r}-by-@var{c} sparse matrix with a random distribution |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
252 of @var{n} (<@var{r}) elements per column. The elements of the vectors |
| 6421 | 253 do not need to be sorted in any particular order as Octave will sort |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
254 them prior to storing the data. However, pre-sorting the data will |
| 6421 | 255 make the creation of the sparse matrix faster. |
| 5164 | 256 |
| 257 The function @dfn{spconvert} takes a three or four column real matrix. | |
| 258 The first two columns represent the row and column index respectively and | |
| 259 the third and four columns, the real and imaginary parts of the sparse | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
260 matrix. The matrix can contain zero elements and the elements can be |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
261 sorted in any order. Adding zero elements is a convenient way to define |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
262 the size of the sparse matrix. For example: |
| 5164 | 263 |
| 264 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
265 @group |
| 5164 | 266 s = spconvert ([1 2 3 4; 1 3 4 4; 1 2 3 0]') |
| 267 @result{} Compressed Column Sparse (rows=4, cols=4, nnz=3) | |
| 268 (1 , 1) -> 1 | |
| 269 (2 , 3) -> 2 | |
| 270 (3 , 4) -> 3 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
271 @end group |
| 5164 | 272 @end example |
| 273 | |
| 274 An example of creating and filling a matrix might be | |
| 275 | |
| 276 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
277 @group |
| 5164 | 278 k = 5; |
| 279 nz = r * k; | |
| 280 s = spalloc (r, c, nz) | |
| 281 for j = 1:c | |
| 282 idx = randperm (r); | |
| 5648 | 283 s (:, j) = [zeros(r - k, 1); ... |
| 284 rand(k, 1)] (idx); | |
| 5164 | 285 endfor |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
286 @end group |
| 5164 | 287 @end example |
| 288 | |
| 5324 | 289 It should be noted, that due to the way that the Octave |
| 5164 | 290 assignment functions are written that the assignment will reallocate |
| 5506 | 291 the memory used by the sparse matrix at each iteration of the above loop. |
| 292 Therefore the @dfn{spalloc} function ignores the @var{nz} argument and | |
|
10791
3140cb7a05a1
Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents:
10711
diff
changeset
|
293 does not pre-assign the memory for the matrix. Therefore, it is vitally |
| 5648 | 294 important that code using to above structure should be vectorized |
| 295 as much as possible to minimize the number of assignments and reduce the | |
| 5164 | 296 number of memory allocations. |
| 297 | |
| 6620 | 298 @DOCSTRING(full) |
| 299 | |
| 300 @DOCSTRING(spalloc) | |
| 301 | |
| 302 @DOCSTRING(sparse) | |
| 303 | |
| 304 @DOCSTRING(spconvert) | |
| 305 | |
|
8106
8a42498edb30
Clarify doc for sparse function
David Bateman <dbateman@free.fr>
parents:
7681
diff
changeset
|
306 The above problem of memory reallocation can be avoided in |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
307 oct-files. However, the construction of a sparse matrix from an oct-file |
| 8828 | 308 is more complex than can be discussed here, and |
|
8106
8a42498edb30
Clarify doc for sparse function
David Bateman <dbateman@free.fr>
parents:
7681
diff
changeset
|
309 you are referred to chapter @ref{Dynamically Linked Functions}, to have |
|
8a42498edb30
Clarify doc for sparse function
David Bateman <dbateman@free.fr>
parents:
7681
diff
changeset
|
310 a full description of the techniques involved. |
| 5164 | 311 |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
312 @node Information |
| 5648 | 313 @subsection Finding out Information about Sparse Matrices |
| 314 | |
| 315 There are a number of functions that allow information concerning | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
316 sparse matrices to be obtained. The most basic of these is |
| 5648 | 317 @dfn{issparse} that identifies whether a particular Octave object is |
| 318 in fact a sparse matrix. | |
| 319 | |
| 320 Another very basic function is @dfn{nnz} that returns the number of | |
| 321 non-zero entries there are in a sparse matrix, while the function | |
| 322 @dfn{nzmax} returns the amount of storage allocated to the sparse | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
323 matrix. Note that Octave tends to crop unused memory at the first |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
324 opportunity for sparse objects. There are some cases of user created |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
325 sparse objects where the value returned by @dfn{nzmax} will not be |
| 5648 | 326 the same as @dfn{nnz}, but in general they will give the same |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
327 result. The function @dfn{spstats} returns some basic statistics on |
| 5648 | 328 the columns of a sparse matrix including the number of elements, the |
| 329 mean and the variance of each column. | |
| 330 | |
| 6620 | 331 @DOCSTRING(issparse) |
| 332 | |
| 333 @DOCSTRING(nnz) | |
| 334 | |
| 335 @DOCSTRING(nonzeros) | |
| 336 | |
| 337 @DOCSTRING(nzmax) | |
| 338 | |
| 339 @DOCSTRING(spstats) | |
| 340 | |
| 5648 | 341 When solving linear equations involving sparse matrices Octave |
| 342 determines the means to solve the equation based on the type of the | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
343 matrix as discussed in @ref{Sparse Linear Algebra}. Octave probes the |
| 5648 | 344 matrix type when the div (/) or ldiv (\) operator is first used with |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
345 the matrix and then caches the type. However the @dfn{matrix_type} |
| 5648 | 346 function can be used to determine the type of the sparse matrix prior |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
347 to use of the div or ldiv operators. For example, |
| 5648 | 348 |
| 349 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
350 @group |
| 5648 | 351 a = tril (sprandn(1024, 1024, 0.02), -1) ... |
| 352 + speye(1024); | |
| 353 matrix_type (a); | |
| 354 ans = Lower | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
355 @end group |
| 5648 | 356 @end example |
| 357 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
358 @noindent |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
359 shows that Octave correctly determines the matrix type for lower |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
360 triangular matrices. @dfn{matrix_type} can also be used to force |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
361 the type of a matrix to be a particular type. For example: |
| 5648 | 362 |
| 363 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
364 @group |
| 5648 | 365 a = matrix_type (tril (sprandn (1024, ... |
| 366 1024, 0.02), -1) + speye(1024), 'Lower'); | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
367 @end group |
| 5648 | 368 @end example |
| 369 | |
| 370 This allows the cost of determining the matrix type to be | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
371 avoided. However, incorrectly defining the matrix type will result in |
| 5648 | 372 incorrect results from solutions of linear equations, and so it is |
| 373 entirely the responsibility of the user to correctly identify the | |
| 374 matrix type | |
| 375 | |
| 376 There are several graphical means of finding out information about | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
377 sparse matrices. The first is the @dfn{spy} command, which displays |
| 5648 | 378 the structure of the non-zero elements of the |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
379 matrix. @xref{fig:spmatrix}, for an example of the use of |
| 5704 | 380 @dfn{spy}. More advanced graphical information can be obtained with the |
| 5648 | 381 @dfn{treeplot}, @dfn{etreeplot} and @dfn{gplot} commands. |
| 382 | |
| 383 @float Figure,fig:spmatrix | |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
384 @center @image{spmatrix,4in} |
| 5648 | 385 @caption{Structure of simple sparse matrix.} |
| 386 @end float | |
| 387 | |
| 388 One use of sparse matrices is in graph theory, where the | |
| 7001 | 389 interconnections between nodes are represented as an adjacency |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
390 matrix. That is, if the i-th node in a graph is connected to the j-th |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
391 node. Then the ij-th node (and in the case of undirected graphs the |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
392 ji-th node) of the sparse adjacency matrix is non-zero. If each node |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
393 is then associated with a set of coordinates, then the @dfn{gplot} |
| 5648 | 394 command can be used to graphically display the interconnections |
| 395 between nodes. | |
| 396 | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
397 As a trivial example of the use of @dfn{gplot} consider the example, |
| 5648 | 398 |
| 399 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
400 @group |
| 5648 | 401 A = sparse([2,6,1,3,2,4,3,5,4,6,1,5], |
| 402 [1,1,2,2,3,3,4,4,5,5,6,6],1,6,6); | |
| 403 xy = [0,4,8,6,4,2;5,0,5,7,5,7]'; | |
| 404 gplot(A,xy) | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
405 @end group |
| 5648 | 406 @end example |
| 407 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
408 @noindent |
| 5648 | 409 which creates an adjacency matrix @code{A} where node 1 is connected |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
410 to nodes 2 and 6, node 2 with nodes 1 and 3, etc. The coordinates of |
| 5648 | 411 the nodes are given in the n-by-2 matrix @code{xy}. |
| 412 @ifset htmltex | |
| 413 @xref{fig:gplot}. | |
| 414 | |
| 415 @float Figure,fig:gplot | |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
416 @center @image{gplot,4in} |
| 5648 | 417 @caption{Simple use of the @dfn{gplot} command.} |
| 418 @end float | |
| 419 @end ifset | |
| 420 | |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
421 The dependencies between the nodes of a Cholesky@tie{}factorization can be |
| 5648 | 422 calculated in linear time without explicitly needing to calculate the |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
423 Cholesky@tie{}factorization by the @code{etree} command. This command |
| 5648 | 424 returns the elimination tree of the matrix and can be displayed |
| 425 graphically by the command @code{treeplot(etree(A))} if @code{A} is | |
| 426 symmetric or @code{treeplot(etree(A+A'))} otherwise. | |
| 427 | |
| 6620 | 428 @DOCSTRING(spy) |
| 429 | |
| 430 @DOCSTRING(etree) | |
| 431 | |
| 432 @DOCSTRING(etreeplot) | |
| 433 | |
| 434 @DOCSTRING(gplot) | |
| 435 | |
| 436 @DOCSTRING(treeplot) | |
| 437 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
438 @DOCSTRING(treelayout) |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
439 |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
440 @node Operators and Functions |
| 5164 | 441 @subsection Basic Operators and Functions on Sparse Matrices |
| 442 | |
| 443 @menu | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
444 * Sparse Functions:: |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
445 * Return Types of Operators and Functions:: |
|
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
446 * Mathematical Considerations:: |
| 5164 | 447 @end menu |
| 448 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
449 @node Sparse Functions |
| 5648 | 450 @subsubsection Sparse Functions |
| 451 | |
|
11396
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
452 Many Octave functions have been overloaded to work with either sparse or full |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
453 matrices. There is no difference in calling convention when using an |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
454 overloaded function with a sparse matrix, however, there is also no access to |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
455 potentially sparse-specific features. At any time the sparse matrix specific |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
456 version of a function can be used by explicitly calling its function name. |
| 5648 | 457 |
|
11396
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
458 The table below lists all of the sparse functions of Octave. Note that the |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
459 names of the specific sparse forms of the functions are typically the same as |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
460 the general versions with a @dfn{sp} prefix. In the table below, and in the |
|
7b563cf94d8d
Remove documentation on deprecated function dispatch
Rik <octave@nomad.inbox5.com>
parents:
11392
diff
changeset
|
461 rest of this article, the specific sparse versions of functions are used. |
| 6620 | 462 |
| 463 @c Table includes in comments the missing sparse functions | |
| 5648 | 464 |
| 465 @table @asis | |
| 466 @item Generate sparse matrices: | |
| 467 @dfn{spalloc}, @dfn{spdiags}, @dfn{speye}, @dfn{sprand}, | |
| 468 @dfn{sprandn}, @dfn{sprandsym} | |
| 469 | |
| 470 @item Sparse matrix conversion: | |
|
7505
f5005d9510f4
Remove dispatched sparse functions and treat in the generic versions of the functions
David Bateman <dbateman@free.fr>
parents:
7455
diff
changeset
|
471 @dfn{full}, @dfn{sparse}, @dfn{spconvert} |
| 5648 | 472 |
| 473 @item Manipulate sparse matrices | |
| 474 @dfn{issparse}, @dfn{nnz}, @dfn{nonzeros}, @dfn{nzmax}, | |
| 6620 | 475 @dfn{spfun}, @dfn{spones}, @dfn{spy} |
| 5164 | 476 |
| 5648 | 477 @item Graph Theory: |
| 478 @dfn{etree}, @dfn{etreeplot}, @dfn{gplot}, | |
| 6620 | 479 @dfn{treeplot} |
| 480 @c @dfn{treelayout} | |
| 5648 | 481 |
| 482 @item Sparse matrix reordering: | |
| 7619 | 483 @dfn{amd}, @dfn{ccolamd}, @dfn{colamd}, @dfn{colperm}, @dfn{csymamd}, |
| 6620 | 484 @dfn{dmperm}, @dfn{symamd}, @dfn{randperm}, @dfn{symrcm} |
| 5648 | 485 |
| 486 @item Linear algebra: | |
|
8417
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
487 @dfn{condest}, @dfn{eigs}, @dfn{matrix_type}, @dfn{normest}, @dfn{sprank}, |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
488 @dfn{spaugment}, @dfn{svds} |
| 5648 | 489 |
| 490 @item Iterative techniques: | |
| 6620 | 491 @dfn{luinc}, @dfn{pcg}, @dfn{pcr} |
| 492 @c @dfn{bicg}, @dfn{bicgstab}, @dfn{cholinc}, @dfn{cgs}, @dfn{gmres}, | |
| 493 @c @dfn{lsqr}, @dfn{minres}, @dfn{qmr}, @dfn{symmlq} | |
| 5648 | 494 |
| 495 @item Miscellaneous: | |
|
7515
f3c00dc0912b
Eliminate the rest of the dispatched sparse functions
David Bateman <dbateman@free.fr>
parents:
7505
diff
changeset
|
496 @dfn{spparms}, @dfn{symbfact}, @dfn{spstats} |
| 5648 | 497 @end table |
| 498 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
499 In addition all of the standard Octave mapper functions (i.e., basic |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
500 math functions that take a single argument) such as @dfn{abs}, etc. |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
501 can accept sparse matrices. The reader is referred to the documentation |
| 5648 | 502 supplied with these functions within Octave itself for further |
| 503 details. | |
| 5164 | 504 |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
505 @node Return Types of Operators and Functions |
| 5164 | 506 @subsubsection The Return Types of Operators and Functions |
| 507 | |
| 5506 | 508 The two basic reasons to use sparse matrices are to reduce the memory |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
509 usage and to not have to do calculations on zero elements. The two are |
| 5164 | 510 closely related in that the computation time on a sparse matrix operator |
| 5506 | 511 or function is roughly linear with the number of non-zero elements. |
| 5164 | 512 |
| 513 Therefore, there is a certain density of non-zero elements of a matrix | |
| 514 where it no longer makes sense to store it as a sparse matrix, but rather | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
515 as a full matrix. For this reason operators and functions that have a |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
516 high probability of returning a full matrix will always return one. For |
| 5164 | 517 example adding a scalar constant to a sparse matrix will almost always |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
518 make it a full matrix, and so the example, |
| 5164 | 519 |
| 520 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
521 @group |
| 5164 | 522 speye(3) + 0 |
| 523 @result{} 1 0 0 | |
| 524 0 1 0 | |
| 525 0 0 1 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
526 @end group |
| 5164 | 527 @end example |
| 528 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
529 @noindent |
| 7330 | 530 returns a full matrix as can be seen. |
| 531 | |
| 532 | |
| 533 Additionally, if @code{sparse_auto_mutate} is true, all sparse functions | |
| 534 test the amount of memory occupied by the sparse matrix to see if the | |
| 535 amount of storage used is larger than the amount used by the full | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
536 equivalent. Therefore @code{speye (2) * 1} will return a full matrix as |
| 5164 | 537 the memory used is smaller for the full version than the sparse version. |
| 538 | |
| 539 As all of the mixed operators and functions between full and sparse | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
540 matrices exist, in general this does not cause any problems. However, |
| 5164 | 541 one area where it does cause a problem is where a sparse matrix is |
| 542 promoted to a full matrix, where subsequent operations would resparsify | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
543 the matrix. Such cases are rare, but can be artificially created, for |
| 5164 | 544 example @code{(fliplr(speye(3)) + speye(3)) - speye(3)} gives a full |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
545 matrix when it should give a sparse one. In general, where such cases |
| 5164 | 546 occur, they impose only a small memory penalty. |
| 547 | |
| 5648 | 548 There is however one known case where this behavior of Octave's |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
549 sparse matrices will cause a problem. That is in the handling of the |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
550 @dfn{diag} function. Whether @dfn{diag} returns a sparse or full matrix |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
551 depending on the type of its input arguments. So |
| 5164 | 552 |
| 553 @example | |
| 554 a = diag (sparse([1,2,3]), -1); | |
| 555 @end example | |
| 556 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
557 @noindent |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
558 should return a sparse matrix. To ensure this actually happens, the |
| 5164 | 559 @dfn{sparse} function, and other functions based on it like @dfn{speye}, |
| 560 always returns a sparse matrix, even if the memory used will be larger | |
| 561 than its full representation. | |
| 562 | |
| 7330 | 563 @DOCSTRING(sparse_auto_mutate) |
| 564 | |
| 565 Note that the @code{sparse_auto_mutate} option is incompatible with | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
566 @sc{matlab}, and so it is off by default. |
| 7330 | 567 |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
568 @node Mathematical Considerations |
| 5164 | 569 @subsubsection Mathematical Considerations |
| 570 | |
| 571 The attempt has been made to make sparse matrices behave in exactly the | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
572 same manner as there full counterparts. However, there are certain differences |
| 5164 | 573 and especially differences with other products sparse implementations. |
| 574 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
575 Firstly, the "./" and ".^" operators must be used with care. Consider what |
| 5164 | 576 the examples |
| 577 | |
| 578 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
579 @group |
| 5164 | 580 s = speye (4); |
| 581 a1 = s .^ 2; | |
| 582 a2 = s .^ s; | |
| 583 a3 = s .^ -2; | |
| 584 a4 = s ./ 2; | |
| 585 a5 = 2 ./ s; | |
| 586 a6 = s ./ s; | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
587 @end group |
| 5164 | 588 @end example |
| 589 | |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10828
diff
changeset
|
590 @noindent |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
591 will give. The first example of @var{s} raised to the power of 2 causes |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
592 no problems. However @var{s} raised element-wise to itself involves a |
| 6431 | 593 large number of terms @code{0 .^ 0} which is 1. There @code{@var{s} .^ |
| 5164 | 594 @var{s}} is a full matrix. |
| 595 | |
|
8347
fa78cb8d8a5c
corrections for typos
Brian Gough<bjg@network-theory.co.uk>
parents:
8286
diff
changeset
|
596 Likewise @code{@var{s} .^ -2} involves terms like @code{0 .^ -2} which |
| 5164 | 597 is infinity, and so @code{@var{s} .^ -2} is equally a full matrix. |
| 598 | |
| 599 For the "./" operator @code{@var{s} ./ 2} has no problems, but | |
| 600 @code{2 ./ @var{s}} involves a large number of infinity terms as well | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
601 and is equally a full matrix. The case of @code{@var{s} ./ @var{s}} |
| 5164 | 602 involves terms like @code{0 ./ 0} which is a @code{NaN} and so this |
| 603 is equally a full matrix with the zero elements of @var{s} filled with | |
| 604 @code{NaN} values. | |
| 605 | |
| 5648 | 606 The above behavior is consistent with full matrices, but is not |
| 5164 | 607 consistent with sparse implementations in other products. |
| 608 | |
| 609 A particular problem of sparse matrices comes about due to the fact that | |
| 610 as the zeros are not stored, the sign-bit of these zeros is equally not | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
611 stored. In certain cases the sign-bit of zero is important. For example: |
| 5164 | 612 |
| 613 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
614 @group |
| 5164 | 615 a = 0 ./ [-1, 1; 1, -1]; |
| 616 b = 1 ./ a | |
| 617 @result{} -Inf Inf | |
| 618 Inf -Inf | |
| 619 c = 1 ./ sparse (a) | |
| 620 @result{} Inf Inf | |
| 621 Inf Inf | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
622 @end group |
| 5164 | 623 @end example |
| 624 | |
| 5648 | 625 To correct this behavior would mean that zero elements with a negative |
| 5164 | 626 sign-bit would need to be stored in the matrix to ensure that their |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
627 sign-bit was respected. This is not done at this time, for reasons of |
| 6750 | 628 efficiency, and so the user is warned that calculations where the sign-bit |
| 5164 | 629 of zero is important must not be done using sparse matrices. |
| 630 | |
| 5648 | 631 In general any function or operator used on a sparse matrix will |
| 632 result in a sparse matrix with the same or a larger number of non-zero | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
633 elements than the original matrix. This is particularly true for the |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
634 important case of sparse matrix factorizations. The usual way to |
| 5648 | 635 address this is to reorder the matrix, such that its factorization is |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
636 sparser than the factorization of the original matrix. That is the |
| 5648 | 637 factorization of @code{L * U = P * S * Q} has sparser terms @code{L} |
| 638 and @code{U} than the equivalent factorization @code{L * U = S}. | |
| 639 | |
| 640 Several functions are available to reorder depending on the type of the | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
641 matrix to be factorized. If the matrix is symmetric positive-definite, |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
642 then @dfn{symamd} or @dfn{csymamd} should be used. Otherwise |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
643 @dfn{amd}, @dfn{colamd} or @dfn{ccolamd} should be used. For completeness |
| 5648 | 644 the reordering functions @dfn{colperm} and @dfn{randperm} are |
| 645 also available. | |
| 646 | |
| 8829 | 647 @xref{fig:simplematrix}, for an example of the structure of a simple |
| 5648 | 648 positive definite matrix. |
| 5506 | 649 |
| 5648 | 650 @float Figure,fig:simplematrix |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
651 @center @image{spmatrix,4in} |
| 5648 | 652 @caption{Structure of simple sparse matrix.} |
| 653 @end float | |
| 5506 | 654 |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
655 The standard Cholesky@tie{}factorization of this matrix can be |
| 5648 | 656 obtained by the same command that would be used for a full |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
657 matrix. This can be visualized with the command |
| 5652 | 658 @code{r = chol(A); spy(r);}. |
| 659 @xref{fig:simplechol}. | |
| 660 The original matrix had | |
| 5648 | 661 @ifinfo |
| 662 @ifnothtml | |
| 663 43 | |
| 664 @end ifnothtml | |
| 665 @end ifinfo | |
| 666 @ifset htmltex | |
| 667 598 | |
| 668 @end ifset | |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
669 non-zero terms, while this Cholesky@tie{}factorization has |
| 5648 | 670 @ifinfo |
| 671 @ifnothtml | |
| 672 71, | |
| 673 @end ifnothtml | |
| 674 @end ifinfo | |
| 675 @ifset htmltex | |
| 676 10200, | |
| 677 @end ifset | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
678 with only half of the symmetric matrix being stored. This |
| 5648 | 679 is a significant level of fill in, and although not an issue |
| 680 for such a small test case, can represents a large overhead | |
| 681 in working with other sparse matrices. | |
| 5164 | 682 |
| 5648 | 683 The appropriate sparsity preserving permutation of the original |
| 684 matrix is given by @dfn{symamd} and the factorization using this | |
| 685 reordering can be visualized using the command @code{q = symamd(A); | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
686 r = chol(A(q,q)); spy(r)}. This gives |
| 5648 | 687 @ifinfo |
| 688 @ifnothtml | |
| 689 29 | |
| 690 @end ifnothtml | |
| 691 @end ifinfo | |
| 692 @ifset htmltex | |
| 693 399 | |
| 694 @end ifset | |
| 695 non-zero terms which is a significant improvement. | |
| 5164 | 696 |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
697 The Cholesky@tie{}factorization itself can be used to determine the |
| 5648 | 698 appropriate sparsity preserving reordering of the matrix during the |
| 699 factorization, In that case this might be obtained with three return | |
| 700 arguments as r@code{[r, p, q] = chol(A); spy(r)}. | |
| 5164 | 701 |
| 5648 | 702 @float Figure,fig:simplechol |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
703 @center @image{spchol,4in} |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
704 @caption{Structure of the un-permuted Cholesky@tie{}factorization of the above matrix.} |
| 5648 | 705 @end float |
| 5164 | 706 |
| 5648 | 707 @float Figure,fig:simplecholperm |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
708 @center @image{spcholperm,4in} |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
709 @caption{Structure of the permuted Cholesky@tie{}factorization of the above matrix.} |
| 5648 | 710 @end float |
| 5164 | 711 |
| 5648 | 712 In the case of an asymmetric matrix, the appropriate sparsity |
| 713 preserving permutation is @dfn{colamd} and the factorization using | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
714 this reordering can be visualized using the command |
|
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
715 @code{q = colamd(A); [l, u, p] = lu(A(:,q)); spy(l+u)}. |
| 5164 | 716 |
| 5648 | 717 Finally, Octave implicitly reorders the matrix when using the div (/) |
| 718 and ldiv (\) operators, and so no the user does not need to explicitly | |
| 719 reorder the matrix to maximize performance. | |
| 720 | |
| 7619 | 721 @DOCSTRING(amd) |
| 722 | |
| 6620 | 723 @DOCSTRING(ccolamd) |
| 724 | |
| 725 @DOCSTRING(colamd) | |
| 726 | |
| 727 @DOCSTRING(colperm) | |
| 728 | |
| 729 @DOCSTRING(csymamd) | |
| 730 | |
| 731 @DOCSTRING(dmperm) | |
| 732 | |
| 733 @DOCSTRING(symamd) | |
| 734 | |
| 735 @DOCSTRING(symrcm) | |
| 736 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
737 @node Sparse Linear Algebra |
| 5164 | 738 @section Linear Algebra on Sparse Matrices |
| 739 | |
|
8488
cdb4788879b3
[docs] poly-morphic => polymorphic
Brian Gough <bjg@gnu.org>
parents:
8417
diff
changeset
|
740 Octave includes a polymorphic solver for sparse matrices, where |
| 5164 | 741 the exact solver used to factorize the matrix, depends on the properties |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
742 of the sparse matrix itself. Generally, the cost of determining the matrix type |
| 5322 | 743 is small relative to the cost of factorizing the matrix itself, but in any |
| 744 case the matrix type is cached once it is calculated, so that it is not | |
| 745 re-determined each time it is used in a linear equation. | |
| 5164 | 746 |
| 747 The selection tree for how the linear equation is solve is | |
| 748 | |
| 749 @enumerate 1 | |
| 5648 | 750 @item If the matrix is diagonal, solve directly and goto 8 |
| 5164 | 751 |
| 752 @item If the matrix is a permuted diagonal, solve directly taking into | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
753 account the permutations. Goto 8 |
| 5164 | 754 |
| 5648 | 755 @item If the matrix is square, banded and if the band density is less |
| 756 than that given by @code{spparms ("bandden")} continue, else goto 4. | |
| 5164 | 757 |
| 758 @enumerate a | |
| 759 @item If the matrix is tridiagonal and the right-hand side is not sparse | |
| 5648 | 760 continue, else goto 3b. |
| 5164 | 761 |
| 762 @enumerate | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
763 @item If the matrix is Hermitian, with a positive real diagonal, attempt |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
764 Cholesky@tie{}factorization using @sc{lapack} xPTSV. |
| 5164 | 765 |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
766 @item If the above failed or the matrix is not Hermitian with a positive |
| 5164 | 767 real diagonal use Gaussian elimination with pivoting using |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
768 @sc{lapack} xGTSV, and goto 8. |
| 5164 | 769 @end enumerate |
| 770 | |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
771 @item If the matrix is Hermitian with a positive real diagonal, attempt |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
772 Cholesky@tie{}factorization using @sc{lapack} xPBTRF. |
| 5164 | 773 |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
774 @item if the above failed or the matrix is not Hermitian with a positive |
| 5164 | 775 real diagonal use Gaussian elimination with pivoting using |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
776 @sc{lapack} xGBTRF, and goto 8. |
| 5164 | 777 @end enumerate |
| 778 | |
| 779 @item If the matrix is upper or lower triangular perform a sparse forward | |
| 5648 | 780 or backward substitution, and goto 8 |
| 5164 | 781 |
|
11573
6f8ffe2c6f76
Grammarcheck txi files for 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
782 @item If the matrix is an upper triangular matrix with column permutations |
| 5322 | 783 or lower triangular matrix with row permutations, perform a sparse forward |
| 5648 | 784 or backward substitution, and goto 8 |
| 5164 | 785 |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
786 @item If the matrix is square, Hermitian with a real positive diagonal, attempt |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
787 sparse Cholesky@tie{}factorization using @sc{cholmod}. |
| 5164 | 788 |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
789 @item If the sparse Cholesky@tie{}factorization failed or the matrix is not |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
790 Hermitian with a real positive diagonal, and the matrix is square, factorize |
|
10711
fbd7843974fa
Periodic grammar check of documentation files to ensure common format.
Rik <octave@nomad.inbox5.com>
parents:
10668
diff
changeset
|
791 using @sc{umfpack}. |
| 5164 | 792 |
| 793 @item If the matrix is not square, or any of the previous solvers flags | |
| 5648 | 794 a singular or near singular matrix, find a minimum norm solution using |
|
10828
322f43e0e170
Grammarcheck .txi documentation files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
795 @sc{cxsparse}@footnote{The @sc{cholmod}, @sc{umfpack} and @sc{cxsparse} packages were |
| 7096 | 796 written by Tim Davis and are available at |
| 797 http://www.cise.ufl.edu/research/sparse/}. | |
| 5164 | 798 @end enumerate |
| 799 | |
| 800 The band density is defined as the number of non-zero values in the matrix | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
801 divided by the number of non-zero values in the matrix. The banded matrix |
| 5164 | 802 solvers can be entirely disabled by using @dfn{spparms} to set @code{bandden} |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
803 to 1 (i.e., @code{spparms ("bandden", 1)}). |
| 5164 | 804 |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
805 The QR@tie{}solver factorizes the problem with a Dulmage-Mendelsohn, to |
| 6939 | 806 separate the problem into blocks that can be treated as over-determined, |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
807 multiple well determined blocks, and a final over-determined block. For |
| 6939 | 808 matrices with blocks of strongly connected nodes this is a big win as |
|
11593
1577c6f80926
Use non-breaking spaces between certain adjectives and their nouns in docstrings.
Rik <octave@nomad.inbox5.com>
parents:
11573
diff
changeset
|
809 LU@tie{}decomposition can be used for many blocks. It also significantly |
| 5681 | 810 improves the chance of finding a solution to over-determined problems |
| 811 rather than just returning a vector of @dfn{NaN}'s. | |
| 812 | |
| 813 All of the solvers above, can calculate an estimate of the condition | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
814 number. This can be used to detect numerical stability problems in the |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
815 solution and force a minimum norm solution to be used. However, for |
| 5681 | 816 narrow banded, triangular or diagonal matrices, the cost of |
| 817 calculating the condition number is significant, and can in fact | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
818 exceed the cost of factoring the matrix. Therefore the condition |
| 6939 | 819 number is not calculated in these cases, and Octave relies on simpler |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
820 techniques to detect singular matrices or the underlying @sc{lapack} code in |
| 5681 | 821 the case of banded matrices. |
| 5164 | 822 |
| 5322 | 823 The user can force the type of the matrix with the @code{matrix_type} |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
824 function. This overcomes the cost of discovering the type of the matrix. |
|
8347
fa78cb8d8a5c
corrections for typos
Brian Gough<bjg@network-theory.co.uk>
parents:
8286
diff
changeset
|
825 However, it should be noted that identifying the type of the matrix incorrectly |
| 5322 | 826 will lead to unpredictable results, and so @code{matrix_type} should be |
| 5506 | 827 used with care. |
| 5322 | 828 |
| 6620 | 829 @DOCSTRING(normest) |
| 830 | |
|
8286
6f2d95255911
fix @seealso references to point to existing anchors
Thorsten Meyer <thorsten.meyier@gmx.de>
parents:
8106
diff
changeset
|
831 @DOCSTRING(onenormest) |
|
6f2d95255911
fix @seealso references to point to existing anchors
Thorsten Meyer <thorsten.meyier@gmx.de>
parents:
8106
diff
changeset
|
832 |
| 7189 | 833 @DOCSTRING(condest) |
| 834 | |
| 6620 | 835 @DOCSTRING(spparms) |
| 836 | |
| 837 @DOCSTRING(sprank) | |
| 838 | |
| 839 @DOCSTRING(symbfact) | |
| 840 | |
|
7681
b1c1133641ee
Add the spaugment function
David Bateman <dbateman@free.fr>
parents:
7619
diff
changeset
|
841 For non square matrices, the user can also utilize the @code{spaugment} |
|
b1c1133641ee
Add the spaugment function
David Bateman <dbateman@free.fr>
parents:
7619
diff
changeset
|
842 function to find a least squares solution to a linear equation. |
|
b1c1133641ee
Add the spaugment function
David Bateman <dbateman@free.fr>
parents:
7619
diff
changeset
|
843 |
|
b1c1133641ee
Add the spaugment function
David Bateman <dbateman@free.fr>
parents:
7619
diff
changeset
|
844 @DOCSTRING(spaugment) |
|
b1c1133641ee
Add the spaugment function
David Bateman <dbateman@free.fr>
parents:
7619
diff
changeset
|
845 |
|
8417
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
846 Finally, the function @code{eigs} can be used to calculate a limited |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
847 number of eigenvalues and eigenvectors based on a selection criteria |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
848 and likewise for @code{svds} which calculates a limited number of |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
849 singular values and vectors. |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
850 |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
851 @DOCSTRING(eigs) |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
852 |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
853 @DOCSTRING(svds) |
|
654bcfb937bf
Add the eigs and svds functions
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
854 |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
855 @node Iterative Techniques |
| 5164 | 856 @section Iterative Techniques applied to sparse matrices |
| 857 | |
| 6620 | 858 The left division @code{\} and right division @code{/} operators, |
| 859 discussed in the previous section, use direct solvers to resolve a | |
| 860 linear equation of the form @code{@var{x} = @var{A} \ @var{b}} or | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
861 @code{@var{x} = @var{b} / @var{A}}. Octave equally includes a number of |
| 6620 | 862 functions to solve sparse linear equations using iterative techniques. |
| 863 | |
| 864 @DOCSTRING(pcg) | |
| 865 | |
| 866 @DOCSTRING(pcr) | |
| 5837 | 867 |
| 6620 | 868 The speed with which an iterative solver converges to a solution can be |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
869 accelerated with the use of a pre-conditioning matrix @var{M}. In this |
| 6620 | 870 case the linear equation @code{@var{M}^-1 * @var{x} = @var{M}^-1 * |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
871 @var{A} \ @var{b}} is solved instead. Typical pre-conditioning matrices |
| 6620 | 872 are partial factorizations of the original matrix. |
| 5648 | 873 |
| 6620 | 874 @DOCSTRING(luinc) |
| 875 | |
|
8817
03b7f618ab3d
include docstrings for new functions in the manual
John W. Eaton <jwe@octave.org>
parents:
8488
diff
changeset
|
876 @node Real Life Example |
| 5648 | 877 @section Real Life Example of the use of Sparse Matrices |
| 878 | |
| 879 A common application for sparse matrices is in the solution of Finite | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
880 Element Models. Finite element models allow numerical solution of |
| 5648 | 881 partial differential equations that do not have closed form solutions, |
| 882 typically because of the complex shape of the domain. | |
| 883 | |
| 884 In order to motivate this application, we consider the boundary value | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
885 Laplace equation. This system can model scalar potential fields, such |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
886 as heat or electrical potential. Given a medium |
| 5648 | 887 @tex |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
888 $\Omega$ with boundary $\partial\Omega$. At all points on the $\partial\Omega$ |
|
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
889 the boundary conditions are known, and we wish to calculate the potential in |
|
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
890 $\Omega$. |
| 5648 | 891 @end tex |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
892 @ifnottex |
|
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
893 Omega with boundary dOmega. At all points on the dOmega |
| 5648 | 894 the boundary conditions are known, and we wish to calculate the potential in |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
895 Omega. |
|
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
896 @end ifnottex |
|
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
897 Boundary conditions may specify the potential (Dirichlet |
| 5648 | 898 boundary condition), its normal derivative across the boundary |
| 899 (Neumann boundary condition), or a weighted sum of the potential and | |
| 900 its derivative (Cauchy boundary condition). | |
| 901 | |
| 902 In a thermal model, we want to calculate the temperature in | |
| 903 @tex | |
| 904 $\Omega$ | |
| 905 @end tex | |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
906 @ifnottex |
| 5648 | 907 Omega |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
908 @end ifnottex |
| 5648 | 909 and know the boundary temperature (Dirichlet condition) |
| 910 or heat flux (from which we can calculate the Neumann condition | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
911 by dividing by the thermal conductivity at the boundary). Similarly, |
| 5648 | 912 in an electrical model, we want to calculate the voltage in |
| 913 @tex | |
| 914 $\Omega$ | |
| 915 @end tex | |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
916 @ifnottex |
| 5648 | 917 Omega |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
918 @end ifnottex |
| 5648 | 919 and know the boundary voltage (Dirichlet) or current |
| 920 (Neumann condition after diving by the electrical conductivity). | |
| 921 In an electrical model, it is common for much of the boundary | |
| 922 to be electrically isolated; this is a Neumann boundary condition | |
| 923 with the current equal to zero. | |
| 924 | |
| 925 The simplest finite element models will divide | |
| 926 @tex | |
| 927 $\Omega$ | |
| 928 @end tex | |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
929 @ifnottex |
| 5648 | 930 Omega |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
931 @end ifnottex |
| 5648 | 932 into simplexes (triangles in 2D, pyramids in 3D). |
| 933 @ifset htmltex | |
|
11573
6f8ffe2c6f76
Grammarcheck txi files for 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
934 We take as a 3-D example a cylindrical liquid filled tank with a small |
| 5648 | 935 non-conductive ball from the EIDORS project@footnote{EIDORS - Electrical |
| 936 Impedance Tomography and Diffuse optical Tomography Reconstruction Software | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
937 @url{http://eidors3d.sourceforge.net}}. This is model is designed to reflect |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
938 an application of electrical impedance tomography, where current patterns |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
939 are applied to such a tank in order to image the internal conductivity |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
940 distribution. In order to describe the FEM geometry, we have a matrix of |
| 5648 | 941 vertices @code{nodes} and simplices @code{elems}. |
| 942 @end ifset | |
| 943 | |
|
11573
6f8ffe2c6f76
Grammarcheck txi files for 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
944 The following example creates a simple rectangular 2-D electrically |
| 5648 | 945 conductive medium with 10 V and 20 V imposed on opposite sides |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
946 (Dirichlet boundary conditions). All other edges are electrically |
| 5648 | 947 isolated. |
| 948 | |
| 949 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
950 @group |
| 5648 | 951 node_y= [1;1.2;1.5;1.8;2]*ones(1,11); |
| 952 node_x= ones(5,1)*[1,1.05,1.1,1.2, ... | |
| 953 1.3,1.5,1.7,1.8,1.9,1.95,2]; | |
| 954 nodes= [node_x(:), node_y(:)]; | |
| 955 | |
| 956 [h,w]= size(node_x); | |
| 957 elems= []; | |
| 958 for idx= 1:w-1 | |
| 959 widx= (idx-1)*h; | |
| 960 elems= [elems; ... | |
| 961 widx+[(1:h-1);(2:h);h+(1:h-1)]'; ... | |
| 962 widx+[(2:h);h+(2:h);h+(1:h-1)]' ]; | |
| 963 endfor | |
| 964 | |
| 965 E= size(elems,1); # No. of simplices | |
| 966 N= size(nodes,1); # No. of vertices | |
| 967 D= size(elems,2); # dimensions+1 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
968 @end group |
| 5648 | 969 @end example |
| 970 | |
| 971 This creates a N-by-2 matrix @code{nodes} and a E-by-3 matrix | |
| 972 @code{elems} with values, which define finite element triangles: | |
| 5164 | 973 |
| 5648 | 974 @example |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
975 @group |
| 5648 | 976 nodes(1:7,:)' |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
977 1.00 1.00 1.00 1.00 1.00 1.05 1.05 @dots{} |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
978 1.00 1.20 1.50 1.80 2.00 1.00 1.20 @dots{} |
| 5648 | 979 |
| 980 elems(1:7,:)' | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
981 1 2 3 4 2 3 4 @dots{} |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
982 2 3 4 5 7 8 9 @dots{} |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
983 6 7 8 9 6 7 8 @dots{} |
|
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
984 @end group |
| 5648 | 985 @end example |
| 986 | |
| 987 Using a first order FEM, we approximate the electrical conductivity | |
| 988 distribution in | |
| 989 @tex | |
| 990 $\Omega$ | |
| 991 @end tex | |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
992 @ifnottex |
| 5648 | 993 Omega |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
994 @end ifnottex |
| 5648 | 995 as constant on each simplex (represented by the vector @code{conductivity}). |
| 996 Based on the finite element geometry, we first calculate a system (or | |
| 997 stiffness) matrix for each simplex (represented as 3-by-3 elements on the | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
998 diagonal of the element-wise system matrix @code{SE}. Based on @code{SE} |
| 5648 | 999 and a N-by-DE connectivity matrix @code{C}, representing the connections |
| 7001 | 1000 between simplices and vertices, the global connectivity matrix @code{S} is |
| 5648 | 1001 calculated. |
| 1002 | |
| 1003 @example | |
| 1004 # Element conductivity | |
| 1005 conductivity= [1*ones(1,16), ... | |
| 1006 2*ones(1,48), 1*ones(1,16)]; | |
| 1007 | |
| 1008 # Connectivity matrix | |
| 1009 C = sparse ((1:D*E), reshape (elems', ... | |
| 1010 D*E, 1), 1, D*E, N); | |
| 1011 | |
| 1012 # Calculate system matrix | |
| 1013 Siidx = floor ([0:D*E-1]'/D) * D * ... | |
| 1014 ones(1,D) + ones(D*E,1)*(1:D) ; | |
| 1015 Sjidx = [1:D*E]'*ones(1,D); | |
| 1016 Sdata = zeros(D*E,D); | |
| 1017 dfact = factorial(D-1); | |
| 1018 for j=1:E | |
| 1019 a = inv([ones(D,1), ... | |
| 1020 nodes(elems(j,:), :)]); | |
| 1021 const = conductivity(j) * 2 / ... | |
| 1022 dfact / abs(det(a)); | |
| 1023 Sdata(D*(j-1)+(1:D),:) = const * ... | |
| 1024 a(2:D,:)' * a(2:D,:); | |
| 1025 endfor | |
| 1026 # Element-wise system matrix | |
| 1027 SE= sparse(Siidx,Sjidx,Sdata); | |
| 1028 # Global system matrix | |
| 1029 S= C'* SE *C; | |
| 1030 @end example | |
| 1031 | |
| 1032 The system matrix acts like the conductivity | |
| 1033 @tex | |
| 1034 $S$ | |
| 1035 @end tex | |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
1036 @ifnottex |
| 5648 | 1037 @code{S} |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
1038 @end ifnottex |
| 5648 | 1039 in Ohm's law |
| 1040 @tex | |
| 1041 $SV = I$. | |
| 1042 @end tex | |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
1043 @ifnottex |
| 5648 | 1044 @code{S * V = I}. |
|
10668
72585f1ca7a2
Replace @ifinfo with @ifnottex.
Rik <octave@nomad.inbox5.com>
parents:
10599
diff
changeset
|
1045 @end ifnottex |
| 5648 | 1046 Based on the Dirichlet and Neumann boundary conditions, we are able to |
| 1047 solve for the voltages at each vertex @code{V}. | |
| 1048 | |
| 1049 @example | |
| 1050 # Dirichlet boundary conditions | |
| 1051 D_nodes=[1:5, 51:55]; | |
| 1052 D_value=[10*ones(1,5), 20*ones(1,5)]; | |
| 1053 | |
| 1054 V= zeros(N,1); | |
| 1055 V(D_nodes) = D_value; | |
| 1056 idx = 1:N; # vertices without Dirichlet | |
| 1057 # boundary condns | |
| 1058 idx(D_nodes) = []; | |
| 1059 | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
1060 # Neumann boundary conditions. Note that |
| 5648 | 1061 # N_value must be normalized by the |
| 1062 # boundary length and element conductivity | |
| 1063 N_nodes=[]; | |
| 1064 N_value=[]; | |
| 1065 | |
| 1066 Q = zeros(N,1); | |
| 1067 Q(N_nodes) = N_value; | |
| 1068 | |
| 1069 V(idx) = S(idx,idx) \ ( Q(idx) - ... | |
| 1070 S(idx,D_nodes) * V(D_nodes)); | |
| 1071 @end example | |
| 1072 | |
| 1073 Finally, in order to display the solution, we show each solved voltage | |
| 1074 value in the z-axis for each simplex vertex. | |
| 1075 @ifset htmltex | |
| 1076 @xref{fig:femmodel}. | |
| 1077 @end ifset | |
| 1078 | |
| 1079 @example | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
1080 @group |
| 5648 | 1081 elemx = elems(:,[1,2,3,1])'; |
| 1082 xelems = reshape (nodes(elemx, 1), 4, E); | |
| 1083 yelems = reshape (nodes(elemx, 2), 4, E); | |
| 1084 velems = reshape (V(elemx), 4, E); | |
| 1085 plot3 (xelems,yelems,velems,'k'); | |
| 1086 print ('grid.eps'); | |
|
9066
be150a172010
Cleanup documentation for diagperm.texi, sparse.texi
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
1087 @end group |
| 5648 | 1088 @end example |
| 1089 | |
| 1090 | |
| 1091 @ifset htmltex | |
| 1092 @float Figure,fig:femmodel | |
|
9088
77e71f3da3d6
Fix documentation image printing under new development code
Rik <rdrider0-list@yahoo.com>
parents:
9066
diff
changeset
|
1093 @center @image{grid,4in} |
| 5648 | 1094 @caption{Example finite element model the showing triangular elements. |
| 1095 The height of each vertex corresponds to the solution value.} | |
| 1096 @end float | |
| 1097 @end ifset |