1 2 3\newcommand\sparselineqlist {lin\_eqn$_{1}$,lin\_eqn$_{2}$, \ldots ,lin\_eqn$_{n}$} 4\newcommand\sparsematlist {mat$_{1}$,mat$_{2}$, \ldots ,mat$_{n}$} 5\newcommand\sparseveclist {vec$_{1}$,vec$_{2}$, \ldots ,vec$_{n}$} 6 7\newcommand\sparselazyfootnote{\footnote{The \{\}'s can be omitted.}} 8 9\index{Linear Algebra package} 10 11\subsection{Introduction} 12A very powerful feature of \REDUCE{} is the ease with which matrix 13calculations can be performed. 14This package extends the available matrix feature to enable calculations 15with sparse matrices. This package also provides a selection of 16functions that are useful in the world of linear algebra with respect to 17sparse matrices. 18 19\subsubsection*{Loading the Package} 20The package is loaded by: \texttt{load\_package sparse;} 21 22\subsection{Sparse Matrix Calculations} 23To extend the the syntax to this class of calculations we need to add an 24expression type \texttt{sparse}. 25 26\subsubsection{Sparse Variables} 27\ttindextype{SPARSE}{declaration} 28An identifier may be declared a sparse variable by the declaration 29\texttt{SPARSE}. 30The size of the sparse matrix must be declared explicitly in the matrix 31declaration. For example, 32\begin{verbatim} 33sparse aa(10,1),bb(200,200); 34\end{verbatim} 35declares \texttt{AA} to be a 10 x 1 (column) sparse matrix and \texttt{Y} to 36be a 200 x 200 sparse matrix. 37The declaration \texttt{SPARSE} is similar to the declaration \texttt{MATRIX}. 38Once a symbol is declared to name a sparse matrix, it can not also be 39used to name an array, operator, procedure, or used as an ordinary 40variable. For more information see the Matrix Variables 41section (\ref{sec:core-matrix-variables}). 42 43\subsubsection{Assigning Sparse Matrix Elements} 44Once a matix has been declared a sparse matrix all elements of the 45matrix are initialized to 0. Thus when a sparse matrix is initially 46referred to the message 47\begin{verbatim} 48"The matrix is dense, contains only zeros" 49\end{verbatim} 50is returned. When printing out a matrix only the non-zero elements are 51printed. This is due to the fact that only the non-zero elements of the 52matrix are stored. 53To assign the elements of the declared matrix we use the following 54syntax. Assuming \texttt{AA} and \texttt{BB} have been declared as spasre 55matrices, we simply write, 56\begin{verbatim} 57aa(1,1):=10; 58bb(100,150):=a; 59\end{verbatim} 60etc. This then sets the element in the first row and first column to 10, 61or the element in the 100th row and 150th column to \texttt{a}. 62 63\subsubsection{Evaluating Sparse Matrix Elements} 64Once an element of a sparse matrix has been assingned, it may be referred 65to in standard array element notation. Thus \texttt{aa(2,1)} refers to the 66element in the second row and first column of the sparse matrix \texttt{AA}. 67 68\subsection{Sparse Matrix Expressions} 69These follow the normal rules of matrix algebra. Sums and products must 70be of compatible size; otherwise an error will result during evaluation. 71Similarly, only square matrices may be raised to a power. 72A negative power is computed as the inverse of the matrix raised to the 73corresponding positive power. For more information and the syntax for 74matrix algebra see the Matrix Expressions section (\ref{sec:core-matrix-expressions}). 75 76\subsection{Operators with Sparse Matrix Arguments} 77The operators in the Sparse Matix Package are the same as those in the 78Matrix Packge with the exception that the \texttt{NULLSPACE} operator is 79not defined. See section Operators with Matrix Arguments 80(\ref{sec:core-matrix-operators}) for more details. 81 82\subsubsection{Examples} 83In the examples the matrix $\mathcal{AA}$ will be 84 85\( 86\mathcal{AA} = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 870 & 0 & 5 & 0 \\ 0 & 0 & 0 & 9 88\end{array} \right) 89\) 90 91\begin {verbatim} 92det ppp; 93 94135 95 96trace ppp; 97 9818 99 100rank ppp; 101 1024 103 104spmateigen(ppp,eta); 105 106{{eta - 1,1, 107 108 spm(1,1) := arbcomplex(4)$ 109 }, 110 111 {eta - 3,1, 112 113 spm(2,1) := arbcomplex(5)$ 114 }, 115 116 {eta - 5,1, 117 118 spm(3,1) := arbcomplex(6)$ 119 }, 120 121 {eta - 9,1, 122 123 spm(4,1) := arbcomplex(7)$ 124 }} 125\end{verbatim} 126 127\subsection{The Linear Algebra Package for Sparse Matrices} 128This package is an extension of the Linear Algebra Package for \REDUCE{} 129described in section \ref{LINALG}. 130These functions are described 131alphabetically in section \ref{sec:sparse-available-functions}. 132They can be classified into four sections(n.b: the numbers after 133the dots signify the function label in section 6). 134\subsubsection{Basic matrix handling} 135\begin{center} 136\begin{tabular}{l l l l l l} 137spadd\_columns & \ldots & \ref{sparse:spadd_columns} & 138spadd\_rows & \ldots & \ref{sparse:spadd_rows} \\ 139spadd\_to\_columns & \ldots & \ref{sparse:spadd_to_columns} & 140spadd\_to\_rows & \ldots & \ref{sparse:spadd_to_rows} \\ 141spaugment\_columns & \ldots & \ref{sparse:spaugment_columns} & 142spchar\_poly & \ldots & \ref{sparse:spchar_poly} \\ 143spcol\_dim & \ldots & \ref{sparse:spcol_dim} & 144spcopy\_into & \ldots & \ref{sparse:spcopy_into} \\ 145spdiagonal & \ldots & \ref{sparse:spdiagonal} & 146spextend & \ldots & \ref{sparse:spextend} \\ 147spfind\_companion & \ldots & \ref{sparse:spfind_companion} & 148spget\_columns & \ldots & \ref{sparse:spget_columns} \\ 149spget\_rows & \ldots & \ref{sparse:spget_rows} & 150sphermitian\_tp & \ldots & \ref{sparse:sphermitian_tp} \\ 151spmatrix\_augment & \ldots & \ref{sparse:spmatrix_augment} & 152spmatrix\_stack & \ldots & \ref{sparse:spmatrix_stack} \\ 153spminor & \ldots & \ref{sparse:spminor} & 154spmult\_columns & \ldots & \ref{sparse:spmult_columns} \\ 155spmult\_rows & \ldots & \ref{sparse:spmult_rows} & 156sppivot & \ldots & \ref{sparse:sppivot} \\ 157spremove\_columns & \ldots & \ref{sparse:spremove_columns} & 158spremove\_rows & \ldots & \ref{sparse:spremove_rows} \\ 159sprow\_dim & \ldots & \ref{sparse:sprow_dim} & 160sprows\_pivot & \ldots & \ref{sparse:sprows_pivot} \\ 161spstack\_rows & \ldots & \ref{sparse:spstack_rows} & 162spsub\_matrix & \ldots & \ref{sparse:spsub_matrix} \\ 163spswap\_columns & \ldots & \ref{sparse:spswap_columns} & 164spswap\_entries & \ldots & \ref{sparse:spadd_entries} \\ 165spswap\_rows & \ldots & \ref{sparse:spswap_rows} & 166\end{tabular} 167\end{center} 168 169\subsubsection{Constructors} 170 171Functions that create sparse matrices. 172 173\begin{center} 174\begin{tabular}{l l l l l l} 175spband\_matrix & \ldots & \ref{sparse:spband_matrix} & 176spblock\_matrix & \ldots & \ref{sparse:spblock_matrix} \\ 177spchar\_matrix & \ldots & \ref{sparse:spcoeff_matrix} & 178spcoeff\_matrix & \ldots & \ref{sparse:spcoeff_matrix} \\ 179spcompanion & \ldots & \ref{sparse:spcompanion} & 180sphessian & \ldots & \ref{sparse:sphessian} \\ 181spjacobian & \ldots & \ref{sparse:spjacobian} & 182spjordan\_block & \ldots & \ref{sparse:spjordan_block} \\ 183spmake\_identity & \ldots & \ref{sparse:spmake_identity} & 184\end{tabular} 185\end{center} 186 187\subsubsection{High level algorithms} 188 189\begin{center} 190\begin{tabular}{l l l l l l} 191spchar\_poly & \ldots & \ref{sparse:spchar_poly} & 192spcholesky & \ldots & \ref{sparse:spcholesky} \\ 193spgram\_schmidt & \ldots & \ref{sparse:spgram_schmidt} & 194splu\_decom & \ldots & \ref{sparse:splu_decom} \\ 195sppseudo\_inverse & \ldots & \ref{sparse:sppseudo_inverse} & 196spsvd & \ldots & \ref{sparse:spsvd} 197\end{tabular} 198\end{center} 199 200\subsubsection{Predicates} 201 202\begin{center} 203\begin{tabular}{l l l l l l} 204matrixp & \ldots & \ref{sparse:matrixp} & 205sparsematp & \ldots & \ref{sparse:sparsematp} \\ 206squarep & \ldots & \ref{sparse:squarep} & 207symmetricp & \ldots & \ref{sparse:symmetricp} 208\end{tabular} 209\end{center} 210 211\subsubsection*{Note on examples:} 212 213In the examples the matrix $\mathcal{A}$ will be 214 215\( 216\mathcal{A} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix} 217\) 218 219Unfortunately, due to restrictions of size, it is not practical to use 220``large'' sparse matrices in the examples. As a result the examples 221shown may appear trivial, but they give an idea of how the functions 222work. 223 224\subsubsection*{Notation} 225 226Throughout $\mathcal{I}$ is used to indicate the identity matrix and 227$\mathcal{A}^T$ to indicate the transpose of the matrix $\mathcal{A}$. 228 229\subsection{Available Functions} 230\label{sec:sparse-available-functions} 231 232\subsubsection{spadd\_columns, spadd\_rows} 233\label{sparse:spadd_columns} 234\ttindextype{SPADD\_COLUMNS}{operator} 235 236\begin{description} 237\item[Syntax:]\mbox{}\\ 238\texttt{spadd\_columns($\mathcal{A}$,c1,c2,expr);} 239 240\begin{tabular}{l l l} 241$\mathcal{A}$ & :- & a sparse matrix. \\ 242$c1,c2$ & :- & positive integers. \\ 243expr & :- & a scalar expression. 244\end{tabular} 245 246\item[Synopsis:]\mbox{}\\ 247\texttt{spadd\_columns} replaces column $c2$ of $\mathcal{A}$ by\\ 248$\texttt{expr} * \texttt{column($\mathcal{A}$,c1)} + \texttt{column($\mathcal{A}$,c2)}$.\\ 249\texttt{add\_rows} performs the equivalent task on the rows of $\mathcal{A}$. 250 251\item[Examples:]\mbox{}\\ 252\texttt{spadd\_columns}\((\mathcal{A},1,2,x) = 253 \begin{pmatrix} 1 & x & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix}\) \\[2mm] 254\texttt{spadd\_rows}\((\mathcal{A},2,3,5) = 255\begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 25 & 9 \end{pmatrix}\) 256 257\item[Related functions:]\mbox{}\\ 258\texttt{spadd\_to\_columns}, \texttt{spadd\_to\_rows}, 259\texttt{spmult\_columns}, \texttt{spmult\_rows}. 260\end{description} 261 262\subsubsection{spadd\_rows} 263\label{sparse:spadd_rows} 264\ttindextype{SPADD\_ROWS}{operator} 265 266See: \texttt{spadd\_columns}. 267 268 269\subsubsection{spadd\_to\_columns, spadd\_to\_rows} 270\label{sparse:spadd_to_columns} 271\ttindextype{SPADD\_TO\_COLUMNS}{operator} 272 273\begin{description} 274 \item[Syntax:]\mbox{}\\* 275\texttt{spadd\_to\_columns($\mathcal{A}$,column\_list,expr);}\\[2mm] 276\begin{tabular}{l l l} 277$\mathcal{A}$ &:-& a sparse matrix. \\ 278column\_list &:-& a positive integer or a list of positive integers. \\ 279expr &:-& a scalar expression. 280\end{tabular} 281 282\item[Synopsis:]\mbox{}\\* 283\texttt{spadd\_to\_columns} adds expr to each column specified in 284column\_list of $\mathcal{A}$. 285 286\texttt{spadd\_to\_rows} performs the equivalent task on the rows of 287$\mathcal{A}$. 288 289\item[Examples:]\mbox{}\\ 290\texttt{spadd\_to\_columns}\((\mathcal{A},\{1,2\},10) = 291\begin{pmatrix} 11 & 10 & 0 \\ 10 & 15 & 0 \\ 10 & 10 & 9 \end{pmatrix}\) \\[2mm] 292\texttt{spadd\_to\_rows}\((\mathcal{A},2,-x) = 293\begin{pmatrix} 1 & 0 & 0 \\ -x & -x+5 & -x \\ 0 & 0 & 9 \end{pmatrix}\) 294 295\item[Related functions:]\mbox{}\\ 296\texttt{spadd\_columns}, \texttt{spadd\_rows}, \texttt{spmult\_rows}, 297\texttt{spmult\_columns}. 298\end{description} 299 300\subsubsection{spadd\_to\_rows} 301\label{sparse:spadd_to_rows} 302\ttindextype{SPADD\_TO\_ROWS}{operator} 303 304See: \texttt{spadd\_to\_columns}. 305 306 307\subsubsection{spaugment\_columns, spstack\_rows} 308\label{sparse:spaugment_columns} 309\ttindextype{SPAUGMENT\_COLUMNS}{operator} 310 311\begin{description} 312\item[Syntax:]\mbox{}\\ 313 \texttt{spaugment\_columns($\mathcal{A}$,column\_list);}\\[2mm] 314\begin{tabular}{l l l} 315$\mathcal{A}$ &:-& a sparse matrix. \\ 316column\_list &:-& either a positive integer or a list of positive 317 integers. 318\end{tabular} 319 320\item[Synopsis:]\mbox{}\\ 321\texttt{spaugment\_columns} gets hold of the columns of $\mathcal{A}$ specified 322in column\_list and sticks them together. 323 324\texttt{spstack\_rows} performs the same task on rows of 325 $\mathcal{A}$. 326 327\item[Examples:]\mbox{}\\ 328\texttt{spaugment\_columns}\((\mathcal{A},\{1,2\}) = 329\begin{pmatrix} 1 & 0 \\ 0 & 5 \\ 0 & 0 \end{pmatrix}\) \\[2mm] 330\texttt{spstack\_rows}\((\mathcal{A},\{1,3\}) = 331\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 9 \end{pmatrix}\) 332 333\item[Related functions:]\mbox{}\\ 334\texttt{spget\_columns}, \texttt{spget\_rows}, 335\texttt{spsub\_matrix}. 336\end{description} 337 338\subsubsection{spband\_matrix} 339\label{sparse:spband_matrix} 340\ttindextype{SPBAND\_MATRIX}{operator} 341 342\begin{description} 343\item[Syntax:]\mbox{}\\ 344\texttt{spband\_matrix(expr\_list,square\_size);}\\[2mm] 345\begin{tabular}{l l p{.72\linewidth}} 346expr\_list &:-& 347either a single scalar expression or a list of an odd number of scalar 348expressions.\\ 349square\_size &:-& a positive integer. 350\end{tabular} 351 352\item[Synopsis:]\mbox{}\\ 353 \texttt{spband\_matrix} creates a sparse square matrix of 354 dimension square\_size. 355 356\item[Examples:] 357\texttt{spband\_matrix}\((\{x,y,z\},6) = 358\begin{pmatrix} y & z & 0 & 0 & 0 & 0 \\ x & y & z & 0 & 0 359& 0 \\ 0 & x & y & z & 0 & 0 \\ 0 & 0 & x & y & z & 0 \\ 0 & 0 & 0 & x & 360 y & z \\ 0 & 0 & 0 & 0 & x & y 361\end{pmatrix}\) 362 363\item[Related functions:]\mbox{}\\ 364 \texttt{spdiagonal}. 365\end{description} 366 367\subsubsection{spblock\_matrix} 368\label{sparse:spblock_matrix} 369\ttindextype{SPBLOCK\_MATRIX}{operator} 370 371\begin{description} 372 373\item[Syntax:]\mbox{}\\ 374\texttt{spblock\_matrix(r,c,matrix\_list);}\\[2mm] 375\begin{tabular}{l l l} 376r,c &:-& positive integers. \\ 377matrix\_list &:-& a list of matrices of either sparse or matrix type. 378\end{tabular} 379 380\item[Synopsis:]\mbox{}\\ 381\texttt{spblock\_matrix} creates a sparse matrix that consists of r by c matrices 382filled from the matrix\_list row wise. 383 384\item[Examples:]\mbox{}\\ 385\(\mathcal{B} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \,\, 386 \mathcal{C} = \begin{pmatrix} 5 \\ 0 \end{pmatrix}, \,\, 387 \mathcal{D} = \begin{pmatrix} 22 & 0 \\ 0 & 0 \end{pmatrix}\) \\[2mm] 388\texttt{spblock\_matrix}\((2,3,\{\mathcal{B,C,D,D,C,B}\}) = 389\begin{pmatrix} 1 & 0 & 5 & 22 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 39022 & 0 & 5 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 391\end{pmatrix}\) 392\end{description} 393 394\subsubsection{spchar\_matrix} 395\label{sparse:spchar_matrix} 396\ttindextype{SPCHAR\_MATRIX}{operator} 397 398\begin{description} 399\item[Syntax:]\mbox{}\\ 400\texttt{spchar\_matrix($\mathcal{A},\lambda$);}\\[2mm] 401\begin{tabular}{l l l} 402$\mathcal{A}$ &:-& a square sparse matrix. \\ 403$\lambda$ &:-& a symbol or algebraic expression. 404\end{tabular} 405 406\item[Synopsis:]\mbox{}\\ 407\texttt{spchar\_matrix} creates the characteristic matrix $\mathcal{C}$ of 408$\mathcal{A}$. 409 410This is $\mathcal{C} = \lambda * \mathcal{I} - \mathcal{A}$. 411 412\item[Examples:] 413\texttt{spchar\_matrix}\((\mathcal{A},x) = 414\begin{pmatrix} x-1 & 0 & 0 \\ 0 & x-5 & 0 \\ 0 & 0 & x-9 \end{pmatrix}\) 415 416\item[Related functions:]\mbox{}\\ 417\texttt{spchar\_poly}. 418\end{description} 419 420\subsubsection{spchar\_poly} 421\label{sparse:spchar_poly} 422\ttindextype{SPCHAR\_POLY}{operator} 423 424\begin{description} 425\item[Syntax:]\mbox{}\\ 426\texttt{spchar\_poly($\mathcal{A},\lambda$);}\\[2mm] 427\begin{tabular}{l l l} 428$\mathcal{A}$ &:-& a sparse square matrix. \\ 429$\lambda$ &:-& a symbol or algebraic expression. 430\end{tabular} 431 432\item[Synopsis:]\mbox{}\\ 433\texttt{spchar\_poly} finds the characteristic polynomial of 434 $\mathcal{A}$. 435 436This is the determinant of $\lambda * \mathcal{I} - \mathcal{A}$. 437 438\item[Examples:]\mbox{}\\ 439\texttt{spchar\_poly($\mathcal{A}$,$x$)} $= x^3-15*x^2-59*x-45$ 440 441\item[Related functions:]\mbox{}\\ 442\texttt{spchar\_matrix}. 443\end{description} 444 445\subsubsection{spcholesky} 446\label{sparse:spcholesky} 447\ttindextype{SPCHOLESKY}{operator} 448 449\begin{description} 450\item[Syntax:]\mbox{}\\ 451\texttt{spcholesky($\mathcal{A}$);}\\[2mm] 452\begin{tabular}{l l l} 453$\mathcal{A}$ &:-& a positive definite sparse matrix containing numeric entries. 454\end{tabular} 455 456\item[Synopsis:]\mbox{}\\ 457\texttt{spcholesky} computes the cholesky decomposition of $\mathcal{A}$. 458 459It returns \{$\mathcal{L,U}$\} where $\mathcal{L}$ 460is a lower matrix, $\mathcal{U}$ is an upper matrix, \\ $\mathcal{A} = 461\mathcal{LU}$, and $\mathcal{U} = \mathcal{L}^T$. 462 463\item[Examples:]\mbox{}\\ 464\(\mathcal{F} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix}\) \\[2mm] 465\texttt{cholesky}\((\mathcal{F}) = 466\left\{ 467 \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{5} & 0 \\ 0 & 0& 3 \end{pmatrix}, 468 \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{5} & 0 \\ 0 & 0 & 3 \end{pmatrix} 469\right\}\) 470 471\item[Related functions:]\mbox{}\\ 472\texttt{splu\_decom}. 473\end{description} 474 475\subsubsection{spcoeff\_matrix} 476\label{sparse:spcoeff_matrix} 477\ttindextype{SPCOEFF\_MATRIX}{operator} 478 479\begin{description} 480\item[Syntax:]\mbox{}\\ 481\texttt{spcoeff\_matrix(\{\sparselineqlist{}\});} \\[2mm] 482\begin{tabular}{l l p{.435\linewidth}} 483\sparselineqlist &:-& linear equations. Can be 484of the form \textit{equation $=$ number} or just \textit{equation} which is 485equivalent to \textit{equation $=$ 0}. 486\end{tabular} 487 488\item[Synopsis:]\mbox{}\\ 489\texttt{spcoeff\_matrix} creates the coefficient matrix 490 $\mathcal{C}$ of the linear equations. 491 492It returns \{$\mathcal{C,X,B}$\} such that $\mathcal{CX} = \mathcal{B}$. 493 494\item[Examples:]\mbox{}\\ 495\texttt{spcoeff\_matrix}\((\{y-20*w=10,y-z=20,y+4+3*z,w+x+50\}) =\) \\[3mm] 496\(\left\{ \begin{pmatrix} 1 & -20 & 0 & 0 \\ 1 & 0 & -1 & 0 \\ 497 1 & 0 & 3 & 0 \\ 0 & 1 & 0 & 1 498\end{pmatrix}, 499 \begin{pmatrix} y \\ w \\ z \\ x \end{pmatrix}, 500 \begin{pmatrix} 10 \\ 20 \\ -4 \\ 50 \end{pmatrix} \right\}\) 501\end{description} 502 503\subsubsection{spcol\_dim, sprow\_dim} 504\label{sparse:spcol_dim} 505\ttindextype{SPCOL\_DIM}{operator} 506 507\begin{description} 508\item[Syntax:]\mbox{}\\ 509\texttt{column\_dim($\mathcal{A}$);}\\[2mm] 510\begin{tabular}{l l l} 511$\mathcal{A}$ &:-& a sparse matrix. 512\end{tabular} 513 514\item[Synopsis:]\mbox{}\\ 515\texttt{spcol\_dim} finds the column dimension of 516 $\mathcal{A}$. \\ 517\texttt{sprow\_dim} finds the row dimension of $\mathcal{A}$. 518 519\item[Examples:]\mbox{}\\ 520\texttt{spcol\_dim}($\mathcal{A}$) = 3 521\end{description} 522 523\subsubsection{spcompanion} 524\label{sparse:spcompanion} 525\ttindextype{SPCOMPANION}{operator} 526 527\begin{description} 528\item[Syntax:]\mbox{}\\ 529\texttt{spcompanion(poly,x);}\\[2mm] 530\begin{tabular}{l l l} 531poly &:-& a monic univariate polynomial in x. \\ 532x &:-& the variable. 533\end{tabular} 534 535\item[Synopsis:]\mbox{}\\ 536 \texttt{spcompanion} creates the companion matrix $\mathcal{C}$ 537 of poly. 538 539This is the square matrix of dimension $n$, where $n$ is the degree of poly 540w.r.t. $x$. 541The entries of $\mathcal{C}$ are: 542 $\mathcal{C}(i,n) = -\texttt{coeffn}(\texttt{poly},x,i-1)$ for $i = 1 543 \ldots n$, $\mathcal{C}(i,i-1) = 1$ for $i = 2 \ldots n$ and 544 the rest are $0$. 545 546\item[Examples:]\mbox{}\\ 547\texttt{spcompanion}\((x^4+17*x^3-9*x^2+11,x) = 548\begin{pmatrix} 549 0 & 0 & 0 & -11 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 9 \\ 0 & 0 & 1 & -17 550\end{pmatrix} 551\) 552 553\item[Related functions:]\mbox{}\\ 554\texttt{spfind\_companion}. 555\end{description} 556 557\subsubsection{spcopy\_into} 558\label{sparse:spcopy_into} 559\ttindextype{SPCOPY\_INTO}{operator} 560 561\begin{description} 562\item[Syntax:]\mbox{}\\ 563\texttt{spcopy\_into($\mathcal{A,B}$,r,c);}\\[2mm] 564\begin{tabular}{l l l} 565$\mathcal{A,B}$ &:-& matrices of type sparse or matrix. \\ 566r,c &:-& positive integers. 567\end{tabular} 568 569\item[Synopsis:]\mbox{}\\ 570 \texttt{spcopy\_into} copies matrix $\mathcal{A}$ into 571 $\mathcal{B}$ with $\mathcal{A}$(1,1) at $\mathcal{B}$(r,c). 572 573\item[Examples:]\mbox{}\\ 574\(\mathcal{G} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 5750 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 576\end{pmatrix}\) \\[2mm] 577\texttt{spcopy\_into}\((\mathcal{A,G},1,2) = 578\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 579& 9 \\ 0 & 0 & 0 & 0 580\end{pmatrix}\) 581 582\item[Related functions:]\mbox{}\\ 583\texttt{spaugment\_columns}, \texttt{spextend}, \texttt{spmatrix\_augment}, 584\texttt{spmatrix\_stack}, \texttt{spstack\_rows}, \texttt{spsub\_matrix}. 585\end{description} 586 587 588\subsubsection{spdiagonal} 589\label{sparse:spdiagonal} 590\ttindextype{SPDIAGONAL}{operator} 591 592\begin{description} 593\item[Syntax:]\mbox{}\\ 594 \texttt{spdiagonal(\{\sparsematlist{}\});}\sparselazyfootnote{}\\[2mm] 595\begin{tabular}{l l p{.58\linewidth}} 596\sparsematlist &:-& each can be either a scalar 597expr or a square matrix of sparse or matrix type. 598\end{tabular} 599 600\item[Synopsis:]\mbox{}\\ 601 \texttt{spdiagonal} creates a sparse matrix that contains the 602input on the diagonal. 603 604\item[Examples:]\mbox{}\\ 605\(\mathcal{H} = \begin{pmatrix} 66 & 77 \\ 88 & 99 \end{pmatrix}\) \\[2mm] 606\texttt{spdiagonal}\((\{\mathcal{A},x,\mathcal{H}\}) = 607\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 & 0 608& 0 \\ 0 & 0 & 9 & 0 & 0 & 0 \\ 0 & 0 & 0 & x & 0 & 0 \\ 0 & 0 & 0 & 0 609& 66 & 77 \\ 0 & 0 & 0 & 0 & 88 & 99 610\end{pmatrix}\) 611 612\item[Related functions:]\mbox{}\\ 613 \texttt{spjordan\_block}. 614\end{description} 615 616\subsubsection{spextend} 617\label{sparse:spextend} 618\ttindextype{SPEXTEND}{operator} 619 620\begin{description} 621\item[Syntax:]\mbox{}\\ 622 \texttt{spextend($\mathcal{A}$,r,c,expr);}\\[2mm] 623\begin{tabular}{l l l} 624$\mathcal{A}$ &:-& a sparse matrix. \\ 625r,c &:-& positive integers. \\ 626expr &:-& algebraic expression or symbol. 627\end{tabular} 628 629\item[Synopsis:]\mbox{}\\ 630 \texttt{spextend} returns a copy of $\mathcal{A}$ that has been 631 extended by r rows and c columns. The new entries are 632 made equal to expr. 633 634\item[Examples:] 635\texttt{spextend}\((\mathcal{A},1,2,0) = 636\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 & 0 637\\ 0 & 0 & 9 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 638\end{pmatrix}\) 639 640\item[Related functions:]\mbox{}\\ 641\texttt{spcopy\_into}, \texttt{spmatrix\_augment}, 642\texttt{spmatrix\_stack}, \texttt{spremove\_columns}, \texttt{spremove\_rows}. 643 644\end{description} 645 646 647\subsubsection{spfind\_companion} 648\label{sparse:spfind_companion} 649\ttindextype{SPFIND\_COMPANION}{operator} 650 651\begin{description} 652\item[Syntax:]\mbox{}\\ 653 \texttt{spfind\_companion($\mathcal{A}$,x);}\\[2mm] 654\begin{tabular}{l l l} 655$\mathcal{A}$ &:-& a sparse matrix. \\ 656x &:-& the variable. 657\end{tabular} 658 659\item[Synopsis:]\mbox{}\\* 660 Given a sparse companion matrix, \texttt{spfind\_companion} finds the polynomial 661from which it was made. 662 663\item[Examples:]\mbox{}\\ 664\(\mathcal{C} = \begin{pmatrix} 0 & 0 & 0 & -11 \\ 1 & 0 & 0 & 0 665\\ 0 & 1 & 0 & 9 \\ 0 & 0 & 1 & -17 666\end{pmatrix}\) \\[2mm] 667\texttt{spfind\_companion}\((\mathcal{C},x) = x^4+17*x^3-9*x^2+11\) 668 669\item[Related functions:]\mbox{}\\* 670 \texttt{spcompanion}. 671\end{description} 672 673\subsubsection{spget\_columns, spget\_rows} 674\label{sparse:spget_columns} 675\ttindextype{SPGET\_COLUMNS}{operator} 676 677\begin{description} 678\item[Syntax:]\mbox{}\\* 679\texttt{spget\_columns($\mathcal{A}$,column\_list);}\\[2mm] 680\begin{tabular}{l l l} 681$\mathcal{A}$ &:-& a sparse matrix. \\ 682c &:-& either a positive integer or a list of positive 683 integers. 684\end{tabular} 685 686\item[Synopsis:]\mbox{}\\* 687\texttt{spget\_columns} removes the columns of $\mathcal{A}$ specified in 688 column\_list and returns them as a list of column 689 matrices. 690 691 \texttt{spget\_rows} performs the same task on the rows of 692 $\mathcal{A}$. 693 694\item[Examples:]\mbox{}\\ 695\texttt{spget\_columns}\((\mathcal{A},\{1,3\}) = 696\left\{ 697 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, 698 \begin{pmatrix} 0 \\ 0 \\ 9 \end{pmatrix} 699\right\}\) \\[2mm] 700\texttt{spget\_rows}\((\mathcal{A},2) = 701\left\{ 702 \begin{pmatrix} 0 & 5 & 0 \end{pmatrix} 703\right\}\) 704 705\item[Related functions:]\mbox{}\\* 706\texttt{spaugment\_columns}, \texttt{spstack\_rows}, 707\texttt{spsub\_matrix}. 708 709\end{description} 710 711\subsubsection{spget\_rows} 712\label{sparse:spget_rows} 713\ttindextype{SPGET\_ROWS}{operator} 714See: \texttt{spget\_columns}. 715 716 717\subsubsection{spgram\_schmidt} 718\label{sparse:spgram_schmidt} 719\ttindextype{SPGRAM\_SCHMIDT}{operator} 720 721\begin{description} 722\item[Syntax:]\mbox{}\\* 723 \texttt{spgram\_schmidt(\{\sparseveclist{}\});}\\[2mm] 724\begin{tabular}{l l p{.62\linewidth}} 725\sparseveclist &:-& linearly independent vectors. 726 Each vector must be written as a list of 727predefined sparse (column) matrices, eg: sparse a(4,1);, a(1,1):=1; 728\end{tabular} 729 730\item[Synopsis:]\mbox{}\\* 731\texttt{spgram\_schmidt} performs the gram\_schmidt 732 orthonormalisation on the input vectors. 733 734It returns a list of orthogonal normalised vectors. 735 736\item[Examples:]\mbox{}\\* 737Suppose a,b,c,d correspond to sparse matrices representing the following 738lists: \{\{1,0,0,0\},\{1,1,0,0\},\{1,1,1,0\},\{1,1,1,1\}\}. 739 740\texttt{spgram\_schmidt(\{\{a\},\{b\},\{c\},\{d\}\})} = \\[1mm] 741 \mbox{}\qquad \{\{1,0,0,0\},\{0,1,0,0\},\{0,0,1,0\},\{0,0,0,1\}\} 742 743\end{description} 744 745\subsubsection{sphermitian\_tp} 746\label{sparse:sphermitian_tp} 747\ttindextype{SPHERMITIAN\_TP}{operator} 748 749\begin{description} 750\item[Syntax:]\mbox{}\\* 751\texttt{sphermitian\_tp($\mathcal{A}$);}\\[2mm] 752\begin{tabular}{l l l} 753$\mathcal{A}$ &:-& a sparse matrix. 754\end{tabular} 755 756\item[Synopsis:]\mbox{}\\* 757 \texttt{sphermitian\_tp} computes the hermitian transpose of 758 $\mathcal{A}$. 759 760\item[Examples:]\mbox{}\\ 761\(\mathcal{J} = \begin{pmatrix} i+1 & i+2 & i+3 \\ 0 & 0 & 0 \\ 0 & i & 0 \end{pmatrix}\) \\[2mm] 762\texttt{sphermitian\_tp}\((\mathcal{J}) = 763\begin{pmatrix} -i+1 & 0 & 0 \\ -i+2 & 0 & -i \\-i+3 & 0 & 0\end{pmatrix}\) 764 765\item[Related functions:]\mbox{}\\* 766\texttt{tp}\footnote{standard reduce call for the 767transpose of a matrix - see section \protect\ref{sec:core-matrix-operators}.}. 768\end{description} 769 770\subsubsection{sphessian} 771\label{sparse:sphessian} 772\ttindextype{SPHESSIAN}{operator} 773 774\begin{description} 775\item[Syntax:]\mbox{}\\* 776 \texttt{sphessian(expr,variable\_list);}\\[2mm] 777\begin{tabular}{l l l} 778expr &:-& a scalar expression. \\ 779variable\_list &:-& either a single variable or a list of variables. 780\end{tabular} 781 782\item[Synopsis:]\mbox{}\\* 783 \texttt{sphessian} computes the hessian matrix of expr w.r.t. 784 the variables in variable\_list. 785 786\item[Examples:] 787\hspace*{0.1in} 788\texttt{sphessian}\((x*y*z+x^2,\{w,x,y,z\}) = 789\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 2 & z & y \\ 0 & z & 0 790& x \\ 0 & y & x & 0 791\end{pmatrix}\) 792\end{description} 793 794\subsubsection{spjacobian} 795\label{sparse:spjacobian} 796\ttindextype{SPJACOBIAN}{operator} 797 798\begin{description} 799\item[Syntax:]\mbox{}\\* 800\texttt{spjacobian(expr\_list,variable\_list);}\\[2mm] 801\begin{tabular}{l l p{.72\linewidth}} 802expr\_list &:-& either a 803single algebraic expression or a list of algebraic expressions.\\ 804variable\_list &:-& either a single variable or a list of variables. 805\end{tabular} 806 807\item[Synopsis:]\mbox{}\\* 808\texttt{spjacobian} computes the jacobian matrix of expr\_list w.r.t. 809variable\_list. 810 811\item[Examples:]\mbox{}\\ 812\texttt{spjacobian}\((\{x^4,x*y^2,x*y*z^3\},\{w,x,y,z\}) =\) \\[2mm] 813\(\begin{pmatrix} 0 & 4*x^3 & 0 & 0 \\ 0 & y^2 & 2*x*y & 0 \\ 8140 & y*z^3 & x*z^3 & 3*x*y*z^2 815\end{pmatrix}\) 816 817\item[Related functions:]\mbox{}\\* 818\texttt{sphessian}, \texttt{df}\footnote{standard reduce call 819for differentiation - see \protect\ref{sec:DF-operator}.}. 820\end{description} 821 822\subsubsection{spjordan\_block} 823\label{sparse:spjordan_block} 824\ttindextype{SPJORDAN\_BLOCK}{operator} 825 826\begin{description} 827\item[Syntax:]\mbox{}\\* 828 \texttt{spjordan\_block(expr,square\_size);}\\[2mm] 829\begin{tabular}{l l l} 830expr &:-& an algebraic expression or symbol. \\ 831square\_size &:-& a positive integer. 832\end{tabular} 833 834\item[Synopsis:]\mbox{}\\* 835\texttt{spjordan\_block} computes the square jordan block matrix $\mathcal{J}$ 836 of dimension square\_size. 837 838\item[Examples:] 839\texttt{spjordan\_block(x,5)} \( = 840\begin{pmatrix} x & 1 & 0 & 0 & 0 \\ 0 & x & 1 & 0 & 0 \\ 0 841& 0 & x & 1 & 0 \\ 0 & 0 & 0 & x & 1 \\ 0 & 0 & 0 & 0 & x 842\end{pmatrix}\) 843 844\item[Related functions:]\mbox{}\\* 845 \texttt{spdiagonal}, \texttt{spcompanion}. 846\end{description} 847 848\subsubsection{splu\_decom} 849\label{sparse:splu_decom} 850\ttindextype{SPLU\_DECOM}{operator} 851 852\begin{description} 853\item[Syntax:]\mbox{}\\* 854\texttt{splu\_decom($\mathcal{A}$);}\\[2mm] 855\begin{tabular}{l l p{.848\linewidth}} 856$\mathcal{A}$ &:-& a sparse matrix containing either 857numeric entries or imaginary entries with numeric coefficients. 858\end{tabular} 859 860\item[Synopsis:]\mbox{}\\* 861 \texttt{splu\_decom} performs LU decomposition on $\mathcal{A}$, 862 ie: it returns \{$\mathcal{L,U}$\} where $\mathcal{L}$ 863 is a lower diagonal matrix, $\mathcal{U}$ an upper diagonal 864 matrix and $\mathcal{A} = \mathcal{LU}$. 865 866\textbf{Caution:} 867The algorithm used can swap the rows of $\mathcal{A}$ 868 during the calculation. This means that $\mathcal{LU}$ does 869 not equal $\mathcal{A}$ but a row equivalent of it. Due to 870 this, \texttt{splu\_decom} returns \{$\mathcal{L,U}$,vec\}. The 871 call \texttt{spconvert($\mathcal{A}$,vec)} will return the 872 sparse matrix that has been decomposed, ie: $\mathcal{LU} = $ 873 \texttt{spconvert($\mathcal{A}$,vec)}. 874 875\item[Examples:] 876\( 877\mathcal{K} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix} 878\) 879 880\texttt{lu}\ $:=$\ \texttt{splu\_decom}\((\mathcal{K}) = 881\left\{ 882 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix}, 883 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, 884 [\; 1 \; 2 \; 3 \; ] 885\right\} 886\) 887 888\(\texttt{first lu * second lu} = 889 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix}\) \\[2mm] 890\(\texttt{convert($\mathcal{K}$,third lu}) = 891 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 \end{pmatrix}\) 892 893\item[Related functions:]\mbox{}\\* 894 \texttt{spcholesky}. 895\end{description} 896 897\subsubsection{spmake\_identity} 898\label{sparse:spmake_identity} 899\ttindextype{SPMAKE\_IDENTITY}{operator} 900 901\begin{description} 902\item[Syntax:]\mbox{}\\* 903 \texttt{spmake\_identity(square\_size);}\\[2mm] 904\begin{tabular}{l l l} 905square\_size &:-& a positive integer. 906\end{tabular} 907 908\item[Synopsis:]\mbox{}\\* 909 \texttt{spmake\_identity} creates the identity matrix of 910 dimension square\_size. 911 912\item[Examples:] 913\texttt{spmake\_identity}\((4) = 914 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 915& 0 & 1 & 0 \\ 0 & 0 & 0 & 1 916\end{pmatrix}\) 917 918\item[Related functions:]\mbox{}\\* 919\texttt{spdiagonal}. 920\end{description} 921 922\subsubsection{spmatrix\_augment, spmatrix\_stack} 923\label{sparse:spmatrix_augment} 924\ttindextype{SPMATRIX\_AUGMENT}{operator} 925 926\begin{description} 927\item[Syntax:]\mbox{}\\* 928 \texttt{spmatrix\_augment(\{\sparsematlist\});}\sparselazyfootnote{}\\[2mm] 929\begin{tabular}{l l l} 930\sparsematlist &:-& matrices. 931\end{tabular} 932 933\item[Synopsis:]\mbox{}\\* 934\texttt{spmatrix\_augment} joins the matrices in 935 matrix\_list together horizontally. 936 937\texttt{spmatrix\_stack} joins the matrices in matrix\_list 938 together vertically. 939 940\item[Examples:]\mbox{}\\ 941\texttt{spmatrix\_augment}\((\{\mathcal{A,A}\}) = 942 \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 5 & 0 943& 0 & 5 & 0 \\ 0 & 0 & 9 & 0 & 0 & 9 944 \end{pmatrix}\) \\[2mm] 945\texttt{spmatrix\_stack}\((\{\mathcal{A,A}\}) = 946 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 947\\ 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9 948 \end{pmatrix}\) 949 950\item[Related functions:]\mbox{}\\* 951 \texttt{spaugment\_columns}, \texttt{spstack\_rows}, 952\texttt{spsub\_matrix}. 953\end{description} 954 955\subsubsection{matrixp} 956\label{sparse:matrixp} 957\ttindex{MATRIXP} 958 959\begin{description} 960\item[Syntax:]\mbox{}\\* 961\texttt{matrixp(test\_input);}\\[2mm] 962\begin{tabular}{l l l} 963test\_input &:-& anything you like. 964\end{tabular} 965 966\item[Synopsis:]\mbox{}\\* 967\texttt{matrixp} is a boolean function that returns t if 968 the input is a matrix of type sparse or matrix and nil otherwise. 969 970\item[Examples:]\mbox{}\\* 971\texttt{matrixp}($\mathcal{A}$) = t 972 973\texttt{matrixp}(doodlesackbanana) = nil 974 975\item[Related functions:]\mbox{}\\* 976\texttt{squarep}, \texttt{symmetricp}, \texttt{sparsematp}. 977\end{description} 978 979\subsubsection{spmatrix\_stack} 980\label{sparse:spmatrix_stack} 981\ttindextype{SPMATRIX\_STACK}{operator} 982See: \texttt{spmatrix\_augment}. 983 984 985\subsubsection{spminor} 986\label{sparse:spminor} 987\ttindextype{SPMINOR}{operator} 988 989\begin{description} 990\item[Syntax:]\mbox{}\\* 991\texttt{spminor($\mathcal{A}$,r,c);}\\[2mm] 992\begin{tabular}{l l l} 993$\mathcal{A}$ &:-& a sparse matrix. \\ 994r,c &:-& positive integers. 995\end{tabular} 996 997\item[Synopsis:]\mbox{}\\* 998 \texttt{spminor} computes the (r,c)'th minor of $\mathcal{A}$. 999 1000\item[Examples:] 1001\texttt{spminor}\((\mathcal{A},1,3) = 1002 \begin{pmatrix} 0 & 5 \\ 0 & 0 \end{pmatrix}\) 1003 1004\item[Related functions:]\mbox{}\\* 1005 \texttt{spremove\_columns}, \texttt{spremove\_rows}. 1006\end{description} 1007 1008\subsubsection{spmult\_columns, spmult\_rows} 1009\label{sparse:spmult_columns} 1010\ttindextype{SPMULT\_COLUMNS}{operator} 1011 1012\begin{description} 1013\item[Syntax:]\mbox{}\\* 1014\texttt{spmult\_columns($\mathcal{A}$,column\_list,expr);}\\[2mm] 1015\begin{tabular}{l l l} 1016$\mathcal{A}$ &:-& a sparse matrix. \\ 1017column\_list &:-& a positive integer or a list of positive integers. \\ 1018expr &:-& an algebraic expression. 1019\end{tabular} 1020 1021\item[Synopsis:]\mbox{}\\* 1022\texttt{spmult\_columns} returns a copy of $\mathcal{A}$ in which 1023 the columns specified in column\_list have been 1024multiplied by expr. 1025 1026\texttt{spmult\_rows} performs the same task on the rows of $\mathcal{A}$. 1027 1028\item[Examples:]\mbox{}\\ 1029\texttt{spmult\_columns}\((\mathcal{A},\{1,3\},x) = 1030 \begin{pmatrix} x & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 9*x \end{pmatrix}\) \\[2mm] 1031\texttt{spmult\_rows}\((\mathcal{A},2,10) = 1032 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 50 & 0 \\ 0 & 0 & 9 \end{pmatrix}\) 1033 1034\item[Related functions:]\mbox{}\\* 1035\texttt{spadd\_to\_columns}, \texttt{spadd\_to\_rows}. 1036\end{description} 1037 1038\subsubsection{spmult\_rows} 1039\label{sparse:spmult_rows} 1040\ttindextype{SPMULT\_ROWS}{operator} 1041 1042See: \texttt{spmult\_columns}. 1043 1044 1045\subsubsection{sppivot} 1046\label{sparse:sppivot} 1047\ttindextype{SPPIVOT}{operator} 1048 1049\begin{description} 1050\item[Syntax:]\mbox{}\\* 1051\texttt{sppivot($\mathcal{A}$,r,c);}\\[2mm] 1052\begin{tabular}{l l l} 1053$\mathcal{A}$ &:-& a sparse matrix. \\ 1054r,c &:-& positive integers such that $\mathcal{A}$(r,c) neq 0. 1055\end{tabular} 1056 1057\item[Synopsis:]\mbox{}\\* 1058\texttt{sppivot} pivots $\mathcal{A}$ about it's (r,c)'th entry. 1059 1060To do this, multiples of the r'th row are added to every 1061 other row in the matrix. 1062 1063This means that the c'th column 1064 will be 0 except for the (r,c)'th entry. 1065 1066\item[Related functions:]\mbox{}\\* 1067\texttt{sprows\_pivot}. 1068\end{description} 1069 1070 1071\subsubsection{sppseudo\_inverse} 1072\label{sparse:sppseudo_inverse} 1073\ttindextype{SPPSEUDO\_INVERSE}{operator} 1074 1075\begin{description} 1076\item[Syntax:]\mbox{}\\* 1077\texttt{sppseudo\_inverse($\mathcal{A}$);}\\[2mm] 1078\begin{tabular}{l l l} 1079$\mathcal{A}$ &:-& a sparse matrix containing only real numeric entries. 1080\end{tabular} 1081 1082\item[Synopsis:]\mbox{}\\* 1083\texttt{sppseudo\_inverse}, also known as the Moore-Penrose inverse, computes 1084the pseudo inverse of $\mathcal{A}$. 1085 1086Given the singular value decomposition of $\mathcal{A}$, i.e: $\mathcal{A} = 1087\mathcal{U} 1088\Sigma\mathcal{V}^T$, then the pseudo inverse $\mathcal{A}^{\dagger}$ is defined 1089by $\mathcal{A}^{\dagger} = \mathcal{V} \Sigma^{\dagger} \mathcal{U}^{T}$. For the 1090diagonal 1091matrix $\Sigma$, the pseudoinverse $\Sigma^{\dagger}$ is computed by taking the reciprocal 1092of only the nonzero diagonal elements. 1093 1094If $\mathcal{A}$ is square and non-singular, then $\mathcal{A}^{\dagger} = \mathcal{A}$. 1095In general, however, 1096$\mathcal{A} \mathcal{A}^{\dagger} \mathcal{A} = \mathcal{A}$, and 1097$\mathcal{A}^{\dagger} \mathcal{A} \mathcal{A}^{\dagger} = \mathcal{A}^{\dagger}$. 1098 1099Perhaps more importantly, $\mathcal{A}^{\dagger}$ solves the following least-squares 1100problem: given a rectangular matrix $\mathcal{A}$ and a vector $b$, find the 1101$x$ minimizing $\|\mathcal{A}x - b\|_2$, 1102and which, in addition, has minimum $\ell_{2}$ (euclidean) Norm, $\|x\|_2$. 1103This $x$ is $\mathcal{A}^{\dagger} b$. 1104 1105\item[Examples:]\mbox{}\\ 1106\(\mathcal{R} = \begin{pmatrix} 0 & 0 & 3 & 0 \\ 9 & 0 & 7 & 0 \end{pmatrix}\) \\[2mm] 1107\texttt{sppseudo\_inverse}\((\mathcal{R}) = 1108 \begin{pmatrix} -0.26 & 0.11 \\ 0 & 0 \\ 0.33 & 0 \\ 0.25 & -0.05 \end{pmatrix}\) 1109 1110\item[Related functions:]\mbox{}\\* 1111 \texttt{spsvd}. 1112\end{description} 1113 1114\subsubsection{spremove\_columns, spremove\_rows} 1115\label{sparse:spremove_columns} 1116\ttindextype{REMOVE\_COLUMNS}{operator} 1117 1118\begin{description} 1119\item[Syntax:]\mbox{}\\* 1120\texttt{spremove\_columns($\mathcal{A}$,column\_list);}\\[2mm] 1121\begin{tabular}{l l l} 1122$\mathcal{A}$ &:-& a sparse matrix. \\ 1123column\_list &:-& either a positive integer or a list of 1124 positive integers. 1125\end{tabular} 1126 1127\item[Synopsis:]\mbox{}\\* 1128\texttt{spremove\_columns} removes the columns specified in 1129 column\_list from $\mathcal{A}$. 1130 1131\texttt{spremove\_rows} performs the same task on the rows 1132 of $\mathcal{A}$. 1133 1134\item[Examples:]\mbox{}\\ 1135\texttt{spremove\_columns}\((\mathcal{A},2) = 1136 \begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 9 \end{pmatrix}\) \\[2mm] 1137\texttt{spremove\_rows}\((\mathcal{A},\{1,3\}) = 1138 \begin{pmatrix} 0 & 5 & 0 \end{pmatrix}\) 1139 1140 1141\item[Related functions:]\mbox{}\\* 1142\texttt{spminor}. 1143\end{description} 1144 1145\subsubsection{spremove\_rows} 1146\label{sparse:spremove_rows} 1147\ttindextype{SPREMOVE\_ROWS}{operator} 1148 1149See: \texttt{spremove\_columns}. 1150 1151 1152\subsubsection{sprow\_dim} 1153\label{sparse:sprow_dim} 1154\ttindextype{SPROW\_DIM}{operator} 1155 1156See: \texttt{spcolumn\_dim}. 1157 1158 1159\subsubsection{sprows\_pivot} 1160\label{sparse:sprows_pivot} 1161\ttindextype{SPROWS\_PIVOT}{operator} 1162 1163\begin{description} 1164\item[Syntax:]\mbox{}\\* 1165\texttt{sprows\_pivot($\mathcal{A}$,r,c,\{row\_list\});}\\[2mm] 1166\begin{tabular}{l l l} 1167$\mathcal{A}$ &:-& a sparse matrix. \\ 1168r,c &:-& positive integers such that $\mathcal{A}$(r,c) neq 0.\\ 1169row\_list &:-& positive integer or a list of positive integers. 1170\end{tabular} 1171 1172\item[Synopsis:]\mbox{}\\* 1173\texttt{sprows\_pivot} performs the same task as \texttt{sppivot} but applies 1174the pivot only to the rows specified in row\_list. 1175 1176\item[Related functions:]\mbox{}\\* 1177\texttt{sppivot}. 1178\end{description} 1179 1180\subsubsection{sparsematp} 1181\label{sparse:sparsematp} 1182\ttindextype{SPARSEMATP}{predicate} 1183 1184\begin{description} 1185\item[Syntax:]\mbox{}\\* 1186\texttt{sparsematp($\mathcal{A}$);}\\[2mm] 1187\begin{tabular}{l l l} 1188$\mathcal{A}$ &:-& a matrix. 1189\end{tabular} 1190 1191\item[Synopsis:]\mbox{}\\* 1192\texttt{sparsematp} is a boolean function that returns t if 1193 the matrix is declared sparse and nil otherwise. 1194 1195\item[Examples:]\mbox{}\\ 1196\(\mathcal{L} := \texttt{mat((1,2,3),(4,5,6),(7,8,9));}\) \\[2mm] 1197\texttt{sparsematp}\((\mathcal{A}) = \texttt{t}\) \\[2mm] 1198\texttt{sparsematp}\((\mathcal{L}) = \texttt{nil}\) 1199 1200\item[Related functions:]\mbox{}\\* 1201\texttt{matrixp}, \texttt{symmetricp}, \texttt{squarep}. 1202\end{description} 1203 1204\subsubsection{squarep} 1205\label{sparse:squarep} 1206\ttindextype{SQUAREP}{predicate} 1207 1208\begin{description} 1209\item[Syntax:]\mbox{}\\* 1210\texttt{squarep($\mathcal{A}$);}\\[2mm] 1211\begin{tabular}{l l l} 1212$\mathcal{A}$ &:-& a matrix. 1213\end{tabular} 1214 1215\item[Synopsis:]\mbox{}\\* 1216\texttt{squarep} is a boolean function that returns t if 1217 the matrix is square and nil otherwise. 1218 1219\item[Examples:]\mbox{}\\ 1220\(\mathcal{L} = \begin{pmatrix} 1 & 3 & 5 \end{pmatrix}\) \\[2mm] 1221\texttt{squarep}\((\mathcal{A}) = \texttt{t}\) \\[2mm] 1222\texttt{squarep}\((\mathcal{L}) = \texttt{nil}\) 1223 1224\item[Related functions:]\mbox{}\\* 1225\texttt{matrixp}, \texttt{symmetricp}, \texttt{sparsematp}. 1226\end{description} 1227 1228 1229\subsubsection{spstack\_rows} 1230\label{sparse:spstack_rows} 1231\ttindextype{STACK\_ROWS}{operator} 1232 1233See: \texttt{spaugment\_columns}. 1234 1235 1236\subsubsection{spsub\_matrix} 1237\label{sparse:spsub_matrix} 1238\ttindextype{SPSUB\_MATRIX}{operator} 1239 1240\begin{description} 1241\item[Syntax:]\mbox{}\\* 1242\texttt{spsub\_matrix($\mathcal{A}$,row\_list,column\_list);}\\[2mm] 1243\begin{tabular}{l l l} 1244$\mathcal{A}$ &:-& a sparse matrix. \\ 1245row\_list, column\_list &:-& \parbox[t]{.605\linewidth}{either a 1246positive integer or a list of positive integers.} 1247\end{tabular} 1248 1249\item[Synopsis:]\mbox{}\\* 1250\texttt{spsub\_matrix} produces the matrix consisting of the 1251 intersection of the rows specified in row\_list and the 1252columns specified in column\_list. 1253 1254\item[Examples:] 1255\hspace*{0.1in} 1256\texttt{spsub\_matrix}\((\mathcal{A},\{1,3\},\{2,3\}) = 1257 \begin{pmatrix} 5 & 0\\ 0 & 9 \end{pmatrix}\) 1258 1259\item[Related functions:]\mbox{}\\* 1260\texttt{spaugment\_columns}, \texttt{spstack\_rows}. 1261\end{description} 1262 1263\subsubsection{spsvd (singular value decomposition)} 1264\label{sparse:spsvd} 1265\ttindextype{SPSVD}{operator} 1266 1267\begin{description} 1268\item[Syntax:]\mbox{}\\* 1269\texttt{spsvd($\mathcal{A}$);}\\[2mm] 1270\begin{tabular}{l l l} 1271$\mathcal{A}$ &:-& a sparse matrix containing only real numeric entries. 1272\end{tabular} 1273 1274\item[Synopsis:]\mbox{}\\* 1275\texttt{spsvd} computes the singular value decomposition of $\mathcal{A}$. 1276 1277If $A$ 1278is an $m\times n$ real matrix of (column) rank $r$, \texttt{svd} returns the 12793-element list \{$\mathcal{U},\Sigma,\mathcal{V}$\} where $\mathcal{A} = 1280\mathcal{U} \Sigma \mathcal{V}^T$. 1281 1282Let $k=\min(m,n)$. Then $U$ is $m\times k$, 1283$V$ is $n\times k$, and and $\Sigma = \mbox{diag}(\sigma_{1}, \ldots ,\sigma_{k})$, 1284where $\sigma_{i}\ge 0$ are the singular values of $\mathcal{A}$; only $r$ of 1285these are non-zero. The singular values are the non-negative square roots of 1286the eigenvalues of $\mathcal{A}^T \mathcal{A}$. 1287 1288$\mathcal{U}$ and $\mathcal{V}$ are such that $\mathcal{UU}^T = \mathcal{VV}^T = 1289\mathcal{V}^T \mathcal{V} = \mathcal{I}_k$. 1290 1291\textbf{Note:} there are a number of different definitions of SVD in the 1292literature, in some of which $\Sigma$ is square and $U$ and $V$ rectangular, as 1293here, but in others $U$ and $V$ are square, and $\Sigma$ is rectangular. 1294 1295\item[Examples:]\mbox{}\\ 1296 \( \mathcal{Q} = \begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix}\) \\[2mm] 1297 \( \mathtt{svd(\mathcal{Q})} = 1298 \left\{ 1299 \begin{pmatrix} -1 & 0 \\ 0 & 0 \end{pmatrix}, 1300 \begin{pmatrix} 1.0 & 0 \\ 0 & 5.0 \end{pmatrix}, 1301 \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} 1302 \right\}\) 1303\end{description} 1304 1305\subsubsection{spswap\_columns, spswap\_rows} 1306\label{sparse:spswap_columns} 1307\ttindextype{SPSWAP\_COLUMNS}{operator} 1308 1309\begin{description} 1310\item[Syntax:]\mbox{}\\* 1311\texttt{spswap\_columns($\mathcal{A}$,c1,c2);}\\[2mm] 1312\begin{tabular}{l l l} 1313$\mathcal{A}$ &:-& a sparse matrix. \\ 1314c1,c1 &:-& positive integers. 1315\end{tabular} 1316 1317\item[Synopsis:]\mbox{}\\* 1318\texttt{spswap\_columns} swaps column c1 of $\mathcal{A}$ with column c2. 1319 1320\texttt{spswap\_rows} performs the same task on 2 rows of 1321 $\mathcal{A}$. 1322 1323\item[Examples:] 1324\texttt{spswap\_columns}\((\mathcal{A},2,3) = 1325 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 5 \\ 0 & 9 & 0 \end{pmatrix}\) 1326 1327\item[Related functions:]\mbox{}\\* 1328\texttt{spswap\_entries}. 1329\end{description} 1330 1331\subsubsection{swap\_entries} 1332\label{sparse:spadd_entries} 1333\ttindextype{SPSWAP\_ENTRIES}{operator} 1334 1335\begin{description} 1336\item[Syntax:]\mbox{}\\* 1337\texttt{spswap\_entries($\mathcal{A}$,\{r1,c1\},\{r2,c2\});}\\[2mm] 1338\begin{tabular}{l l l} 1339$\mathcal{A}$ &:-& a sparse matrix. \\ 1340r1,c1,r2,c2 &:-& positive integers. 1341\end{tabular} 1342 1343\item[Synopsis:]\mbox{}\\* 1344\texttt{spswap\_entries} swaps $\mathcal{A}$(r1,c1) with 1345 $\mathcal{A}$(r2,c2). 1346 1347\item[Examples:] 1348\texttt{spswap\_entries}\((\mathcal{A},\{1,1\},\{3,3\}) = 1349 \begin{pmatrix} 9 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) 1350 1351\item[Related functions:]\mbox{}\\* 1352\texttt{spswap\_columns}, \texttt{spswap\_rows}. 1353 1354 1355\subsubsection{spswap\_rows} 1356\label{sparse:spswap_rows} 1357\ttindextype{SPSWAP\_ROWS}{operator} 1358See: \texttt{spswap\_columns}. 1359\end{description} 1360 1361\subsubsection{symmetricp} 1362\label{sparse:symmetricp} 1363\ttindextype{SYMMETRICP}{predicate} 1364 1365\begin{description} 1366\item[Syntax:]\mbox{}\\* 1367\texttt{symmetricp($\mathcal{A}$);}\\[2mm] 1368\begin{tabular}{l l l} 1369$\mathcal{A}$ &:-& a matrix. 1370\end{tabular} 1371 1372\item[Synopsis:]\mbox{}\\* 1373\texttt{symmetricp} is a boolean function that returns t if the 1374 matrix is symmetric and nil otherwise. 1375 1376\item[Examples:]\mbox{}\\ 1377\(\mathcal{M} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\) \\[2mm] 1378\texttt{symmetricp}\((\mathcal{A}) = \texttt{nil}\) \\[2mm] 1379\texttt{symmetricp}\((\mathcal{M}) = \texttt{t}\) 1380 1381\item[Related functions:]\mbox{}\\* 1382\texttt{matrixp}, \texttt{squarep}, \texttt{sparsematp}. 1383\end{description} 1384 1385 1386\subsection{Fast Linear Algebra} 1387\ttindexswitch[SPARSE]{FAST\_LA} 1388 1389By turning the \sw{fast\_la} switch on, the speed of the following 1390functions will be increased: 1391 1392\begin{tabular}{l l l l} 1393spadd\_columns & spadd\_rows & spaugment\_columns & spcol\_dim \\ 1394spcopy\_into & spmake\_identity & spmatrix\_augment & spmatrix\_stack\\ 1395spminor & spmult\_column & spmult\_row & sppivot \\ 1396spremove\_columns & spremove\_rows & sprows\_pivot & squarep \\ 1397spstack\_rows & spsub\_matrix & spswap\_columns & spswap\_entries\\ 1398spswap\_rows & symmetricp 1399\end{tabular} 1400 1401The increase in speed will be insignificant unless you are making a 1402significant number(i.e: thousands) of calls. When using this switch, 1403error checking is minimised. This means that illegal input may give 1404strange error messages. Beware. 1405 1406\subsection{Acknowledgments} 1407This package is an extention of the code from the Linear Algebra Package 1408for \REDUCE{} by Matt Rebbeck (cf. section \ref{LINALG}). 1409 1410The algorithms for \texttt{spcholesky}, \texttt{splu\_decom}, and \texttt{spsvd} are 1411taken from the book Linear Algebra -- J.H. Wilkinson \& C. Reinsch[3]. 1412 1413The \texttt{spgram\_schmidt} code comes from Karin Gatermann's Symmetry 1414package[4] for {\REDUCE}. 1415