SCM

SCM Repository

[matrix] Annotation of /pkg/inst/doc/Introduction.Rnw
ViewVC logotype

Annotation of /pkg/inst/doc/Introduction.Rnw

Parent Directory Parent Directory | Revision Log Revision Log


Revision 492 - (view) (download)

1 : bates 10 \documentclass{article}
2 :     \usepackage{myVignette}
3 :     \usepackage[authoryear,round]{natbib}
4 :     \bibliographystyle{plainnat}
5 :     %%\VignetteIndexEntry{Introduction to the Matrix Package}
6 :     %%\VignetteDepends{Matrix}
7 :     \SweaveOpts{engine=R,eps=FALSE,pdf=TRUE,width=5,height=3,strip.white=TRUE}
8 :     \title{Introduction to the Matrix package}
9 :     \author{Douglas Bates\\R Core Development Group\\\email{bates@r-project.org}}
10 :     \date{\today}
11 :     \begin{document}
12 :     \maketitle
13 :     \begin{abstract}
14 :     Linear algebra is at the core of many areas of statistical computing
15 :     and from its inception the \Slang{} has supported numerical linear
16 :     algebra via a matrix data type and several functions and operators,
17 :     such as \code{\%*\%}, \code{qr}, \code{chol}, and \code{solve}.
18 :     However, these data types and functions do not provide direct access
19 :     to all of the facilities for efficient manipulation of dense
20 :     matrices, as provided by the Lapack subroutines, and they do not
21 :     provide for manipulation of sparse matrices.
22 :    
23 :     The \code{Matrix} package provides a set of S4 classes for dense and
24 :     sparse matrices that extend the basic matrix data type. Methods for
25 :     a wide variety of functions and operators applied to objects from
26 :     these classes provide efficient access to BLAS (Basic Linear Algebra
27 :     Subroutines), Lapack (dense matrix), TAUCS (sparse matrix) and
28 :     UMFPACK (sparse matrix) routines. One notable characteristic of the
29 :     package is that whenever a matrix is factored, the factorization is
30 :     stored as part of the original matrix so that further operations on
31 :     the matrix can reuse this factorization.
32 :     \end{abstract}
33 :     <<preliminaries, echo=FALSE>>=
34 :     options(width=75)
35 :     @
36 :    
37 :     \section{Introduction}
38 :     \label{sec:Intro}
39 :    
40 :     Linear algebra is at the core of many statistical computing techniques
41 :     and, from its inception, the \Slang{} has supported numerical linear
42 :     algebra via a matrix data type and several functions and operators,
43 :     such as \code{\%*\%}, \code{qr}, \code{chol}, and \code{solve}.
44 :     Initially the numerical linear algebra functions in \RR{} called
45 :     underlying Fortran routines from the Linpack~\citep{Linpack} and
46 :     Eispack~\cite{Eispack} libraries but over the years most of these
47 :     functions have been switched to use routines from the
48 :     Lapack~\cite{Lapack} library. Furthermore, \RR{} can be configured to
49 :     use accelerated BLAS (Basic Linear Algebra Subroutines), such as those
50 :     from the Atlas~\cite{Atlas} project or Goto's BLAS~\cite{GotosBLAS}.
51 :    
52 :     Lapack provides routines for operating on several special forms of
53 :     matrices, such as triangular matrices and symmetric matrices.
54 :     Furthermore,matrix decompositions like the QR decompositions produce
55 :     multiple output components that should be regarded as parts of a
56 :     single object. There is some support in R for operations on special
57 :     forms of matrices (e.g. the \code{backsolve}, \code{forwardsolve} and
58 :     \code{chol2inv} functions) and for special structures (e.g. a QR
59 :     structure is implicitly defined as a list by the \code{qr},
60 :     \code{qr.qy}, \code{qr.qty}, and related functions) but it is not as
61 :     fully developed as it could be.
62 :    
63 :     Also there is no direct support for sparse matrices in R although
64 :     \citet{koen:ng:2003} have developed a contributed package for sparse
65 :     matrices based on SparseKit.
66 :    
67 :     The \code{Matrix} package provides S4 classes and methods for dense
68 :     and sparse matrices. The methods for dense matrices use Lapack and
69 :     BLAS. The sparse matrix methods use TAUCS~\citep{Taucs},
70 :     UMFPACK~\citep{Umfpack}, and Metis~\citep{Metis}.
71 :    
72 :    
73 :     \section{Classes for dense matrices}
74 :     \label{sec:DenseClasses}
75 :    
76 :     The \code{Matrix} package will provide classes for real (stored as
77 :     double precision) and complex (stored as double precision complex)
78 :     dense matrices. At present only the real classes have been
79 :     implemented. These classes are
80 :     \begin{description}
81 : bates 492 \item[dgeMatrix] Real matrices in general storage mode
82 :     \item[dsyMatrix] Symmetric real matrices in non-packed storage
83 :     \item[dtrMatrix] Triangular real matrices in non-packaged storage
84 :     \item[dpoMatrix] Positive semi-definite symmetric real matrices in
85 : bates 10 non-package storage
86 :     \end{description}
87 :     Methods for these classes include coersion between these classes, when
88 :     appropriate, and coersion to the \code{matrix} class; methods for
89 :     matrix multiplication (\code{\%*\%}); cross products
90 :     (\code{crossprod}), matrix norm (\code{norm}); reciprocal condition
91 :     number (\code{rcond}); LU factorization (\code{lu}) or, for the
92 :     \code{poMatrix} class, the Cholesky decomposition (\code{chol}); and
93 :     solutions of linear systems of equations (\code{solve}).
94 :    
95 :     Whenever a factorization or a decomposition is calculated it is
96 : bates 476 preserved as a (list) element in the \code{factors} slot of the
97 : bates 10 original object. In this way a sequence of operations, such as
98 :     determining the condition number of a matrix then solving a linear
99 :     system based on the matrix, do not require multiple factorizations of
100 :     the same matrix nor do they require the user to store the intermediate
101 :     results.
102 :    
103 :    
104 :     \section{Classes for sparse matrices}
105 :     \label{sec:SparseClasses}
106 :    
107 :    
108 :     \subsection{Representations of sparse matrices}
109 :     \label{ssec:SparseReps}
110 :    
111 :     Conceptually, the simplest representation of a sparse matrix is as a
112 :     triplet of an integer vector \code{i} giving the row numbers, an
113 :     integer vector \code{j} giving the column numbers, and a numeric
114 :     vector \code{x} giving the non-zero values in the matrix. An S4 class
115 :     definition might be
116 :     \begin{Schunk}
117 :     \begin{Sinput}
118 : bates 492 setClass("dgTMatrix",
119 : bates 10 representation(i = "integer", j = "integer", x = "numeric",
120 :     Dim = "integer"))
121 :     \end{Sinput}
122 :     \end{Schunk}
123 :    
124 :     The triplet representation is row-oriented if elements in the same row
125 :     were adjacent and column-oriented if elements in the same column were
126 :     adjacent. The compressed sparse row (csr) (or compressed sparse
127 :     column - csc) representation is similar to row-oriented triplet
128 :     (column-oriented triplet) except that \code{i} (\code{j}) just stores
129 :     the index of the first element in the row (column). (There are a
130 :     couple of other details but that is the gist of it.) These compressed
131 :     representations remove the redundant row (column) indices and provide
132 :     faster access to a given location in the matrix because you only need
133 :     to check one row (column).
134 :    
135 :     The preferred representation of sparse matrices in the SparseM package
136 :     is csr. Matlab uses csc. We hope that Octave will also use this
137 :     representation. There are certain advantages to csc in systems like R
138 :     and Matlab where dense matrices are stored in column-major order. For
139 :     example, Sivan Toledo's TAUCS~\cite{Taucs} library and Tim Davis's
140 :     UMFPACK~\cite{Umfpack} library are both based on csc and can both use
141 :     level-3 BLAS in certain sparse matrix computations.
142 :    
143 :     The Matrix package provides the following classes for sparse matrices
144 :     \begin{description}
145 : bates 492 \item[dgTMatrix] general, numeric, sparse matrices in (a possibly
146 : bates 10 redundant) triplet form. This can be a convenient form in which to
147 :     construct sparse matrices.
148 : bates 492 \item[dgCMatrix] general, numeric, sparse matrices in the (sorted) compressed
149 : bates 10 sparse column format.
150 : bates 492 \item[dsCMatrix] symmetric, real, sparse matrices in the (sorted)
151 : bates 10 compressed sparse column format. Only the upper or the lower triangle is
152 :     stored. Although there is provision for both forms, the lower
153 :     triangle form works best with TAUCS.
154 : bates 492 \item[dtCMatrix] triangular, real, sparse matrices in the (sorted)
155 : bates 10 compressed sparse column format.
156 :     \end{description}
157 :    
158 :     \bibliography{Matrix}
159 :     \end{document}

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge