%------------------------------------------------------------------------------- % The CHOLMOD/Doc/UserGuide.tex file. %------------------------------------------------------------------------------- \documentclass[11pt]{article} \batchmode \newcommand{\m}[1]{{\bf{#1}}} % for matrices and vectors \newcommand{\tr}{^{\sf T}} % transpose \newcommand{\new}[1]{\overline{#1}} \topmargin 0in \textheight 8.5in \oddsidemargin 0pt \evensidemargin 0pt \textwidth 6.5in \begin{document} \author{Timothy A. Davis \\ DrTimothyAldenDavis@gmail.com, http://www.suitesparse.com } \title{User Guide for CHOLMOD: a sparse Cholesky factorization and modification package} \input{cholmod_version.tex} \maketitle %------------------------------------------------------------------------------- \begin{abstract} CHOLMOD\footnote{CHOLMOD is short for CHOLesky MODification, since a key feature of the package is its ability to update/downdate a sparse Cholesky factorization} is a set of routines for factorizing sparse symmetric positive definite matrices of the form $\m{A}$ or $\m{AA}\tr$, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system $\m{Lx}=\m{b}$, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. It also includes a non-supernodal $\m{LDL}^T$ factorization method that can factorize symmetric indefinite matrices if all of their leading submatrices are well-conditioned ($\m{D}$ is diagonal). CHOLMOD is written in C11, with both C and MATLAB interfaces. The package works on Linux, Mac, and Windows. \end{abstract} %------------------------------------------------------------------------------- CHOLMOD Copyright\copyright 2005-2023 by Timothy A. Davis, All Rights Reserved. Portions are also copyrighted by William W. Hager (the {\tt Modify} Module), and the University of Florida (the {\tt Partition} Module). All Rights Reserved. See CHOLMOD/Doc/License.txt for the license. CHOLMOD is also available under other licenses that permit its use in proprietary applications; contact the authors for details. See http://www.suitesparse.com for the code and all documentation, including this User Guide. \newpage \tableofcontents %------------------------------------------------------------------------------- \newpage \section{Overview} %------------------------------------------------------------------------------- CHOLMOD is a set of ANSI C routines for solving systems of linear equations, $\m{Ax}=\m{b}$, when $\m{A}$ is sparse and symmetric positive definite, and $\m{x}$ and $\m{b}$ can be either sparse or dense.\footnote{Some support is provided for symmetric indefinite matrices.} Complex matrices are supported, in two different formats. CHOLMOD includes high-performance left-looking supernodal factorization and solve methods \cite{NgPeyton91b}, based on LAPACK \cite{LAPACK} and the BLAS \cite{ACM679a}. After a matrix is factorized, its factors can be updated or downdated using the techniques described by Davis and Hager in \cite{DavisHager99,DavisHager01,DavisHager05}. Many additional sparse matrix operations are provided, for both symmetric and unsymmetric matrices (square or rectangular), including sparse matrix multiply, add, transpose, permutation, scaling, norm, concatenation, sub-matrix access, and converting to alternate data structures. My recent GraphBLAS package will typically be faster for these kinds of operations, however. Interfaces to many ordering methods are provided, including minimum degree (AMD \cite{AmestoyDavisDuff96,AmestoyDavisDuff03}, COLAMD \cite{DavisGilbertLarimoreNg00_algo,DavisGilbertLarimoreNg00}), constrained minimum degree (CSYMAMD, CCOLAMD, CAMD), and graph-partitioning-based nested dissection (METIS \cite{KarypisKumar98}). Most of its operations are available within MATLAB via mexFunction interfaces. CHOLMOD also includes a non-supernodal $\m{LDL}^T$ factorization method that can factorize symmetric indefinite matrices if all of their leading submatrices are well-conditioned ($\m{D}$ is diagonal). A pair of articles on CHOLMOD appears in the ACM Transactions on Mathematical Software: \cite{ChenDavisHagerRajamanickam06,DavisHager06}. CHOLMOD appears as {\tt chol} (the sparse case), {\tt symbfact}, and {\tt etree} in MATLAB 7.2 (R2006a) and later, and is used for {\tt x=A}$\backslash${\tt b} when {\tt A} is symmetric positive definite \cite{GilbertMolerSchreiber}. The C-callable CHOLMOD library consists of many user-callable routines and one include file. Each routine comes in two versions, one for {\tt int32\_t} integers and another for {\tt int64\_t}. Many of the routines can support either real or complex matrices, simply by passing a matrix of the appropriate type. All of the routines support both {\tt double} and single ({\tt float}) precision matrices (this is new in CHOLMOD 5.1). Nick Gould, Yifan Hu, and Jennifer Scott have independently tested CHOLMOD's performance, comparing it with nearly a dozen or so other solvers \cite{GouldHuScott05,GouldHuScott05b}. Its performance was quite competitive. %------------------------------------------------------------------------------- \section{Single-precision sparse matrix support} %------------------------------------------------------------------------------- {\bf CHOLMOD v5.1.0}: introduces full of support for single precision sparse matrices, with the introduction of the new CHOLMOD:Utility Module. The CHOLMOD:Utility Module replaces the CHOLMOD:Core Module that appeared in prior versions of CHOLMOD. %------------------------------------------------------------------------------- \newpage \section{Primary routines and data structures} %------------------------------------------------------------------------------- Five primary CHOLMOD routines are required to factorize $\m{A}$ or $\m{AA}\tr$ and solve the related system $\m{Ax}=\m{b}$ or $\m{AA}\tr\m{x}=\m{b}$, for either the real or complex cases: \begin{enumerate} \item {\tt cholmod\_start}: This must be the first call to CHOLMOD. \item {\tt cholmod\_analyze}: Finds a fill-reducing ordering, and performs the symbolic factorization, either simplicial (non-supernodal) or supernodal. \item {\tt cholmod\_factorize}: Numerical factorization, either simplicial or supernodal, $\m{LL}\tr$ or $\m{LDL}\tr$ using either the symbolic factorization from {\tt cholmod\_analyze} or the numerical factorization from a prior call to {\tt cholmod\_factorize}. \item {\tt cholmod\_solve}: Solves $\m{Ax}=\m{b}$, or many other related systems, where $\m{x}$ and $\m{b}$ are dense matrices. The {\tt cholmod\_spsolve} routine handles the sparse case. Any mixture of real and complex $\m{A}$ and $\m{b}$ are allowed. \item {\tt cholmod\_finish}: This must be the last call to CHOLMOD. \end{enumerate} Additional routines are also required to create and destroy the matrices $\m{A}$, $\m{x}$, $\m{b}$, and the $\m{LL}\tr$ or $\m{LDL}\tr$ factorization. CHOLMOD has five kinds of data structures, referred to as objects and implemented as pointers to {\tt struct}'s: \begin{enumerate} \item {\tt cholmod\_common}: parameter settings, statistics, and workspace used internally by CHOLMOD. See Section~\ref{cholmod_common} for details. \item {\tt cholmod\_sparse}: a sparse matrix in compressed-column form, either pattern-only, real, complex, or ``zomplex.'' In its basic form, the matrix {\tt A} contains: \begin{itemize} \item {\tt A->p}, an integer array of size {\tt A->ncol+1}. \item {\tt A->i}, an integer array of size {\tt A->nzmax}. \item {\tt A->x}, a {\tt double} or {\tt float} array of size {\tt A->nzmax} or twice that for the complex case. This is compatible with the Fortran and ANSI C99 complex data type. \item {\tt A->z}, a {\tt double} or {\tt float} array of size {\tt A->nzmax} if {\tt A} is zomplex. A zomplex matrix has a {\tt z} array, thus the name. This is compatible with the MATLAB representation of complex matrices. \item {\tt A->nz}, an integer array of size {\tt A->ncol}, if {\tt A} is in the {\em unpacked} format. In this format, the columns of {\tt A} can appear out of order, and gaps of unused space can appear between columns. \end{itemize} For all four types of matrices, the row indices of entries of column {\tt j} are located in {\tt A->i [A->p [j] ... A->p [j+1]-1]}, or in {\tt A->i [A->p [j] ... A->p [j] + A->nz [j] -1]}, if in the unpacked format. For a real matrix, the corresponding numerical values are in {\tt A->x} at the same location. For a complex matrix, the entry whose row index is {\tt A->i [p]} is contained in {\tt A->x [2*p]} (the real part) and {\tt A->x [2*p+1]} (the imaginary part). For a zomplex matrix, the real part is in {\tt A->x [p]} and imaginary part is in {\tt A->z [p]}. See Section~\ref{cholmod_sparse} for more details. \item {\tt cholmod\_factor}: A symbolic or numeric factorization, either real, complex, or zomplex. It can be either an $\m{LL}\tr$ or $\m{LDL}\tr$ factorization, and either simplicial or supernodal. You will normally not need to examine its contents. See Section~\ref{cholmod_factor} for more details. \item {\tt cholmod\_dense}: A dense matrix, either real, complex or zomplex, in column-major order. This differs from the row-major convention used in C. A dense matrix {\tt X} contains \begin{itemize} \item {\tt X->x}, a {\tt double} or {\tt float} array of size {\tt X->nzmax} or twice that for the complex case. \item {\tt X->z}, a {\tt double} or {\tt float} array of size {\tt X->nzmax} if {\tt X} is zomplex. \end{itemize} For a real dense matrix $x_{ij}$ is {\tt X->x [i+j*d]} where {\tt d = X->d} is the leading dimension of {\tt X}. For a complex dense matrix, the real part of $x_{ij}$ is {\tt X->x [2*(i+j*d)]} and the imaginary part is {\tt X->x [2*(i+j*d)+1]}. For a zomplex dense matrix, the real part of $x_{ij}$ is {\tt X->x [i+j*d]} and the imaginary part is {\tt X->z [i+j*d]}. Real and complex dense matrices can be passed to LAPACK and the BLAS. See Section~\ref{cholmod_dense} for more details. \item {\tt cholmod\_triplet}: CHOLMOD's sparse matrix ({\tt cholmod\_sparse}) is the primary input for nearly all CHOLMOD routines, but it can be difficult for the user to construct. A simpler method of creating a sparse matrix is to first create a {\tt cholmod\_triplet} matrix, and then convert it to a {\tt cholmod\_sparse} matrix via the {\tt cholmod\_triplet\_to\_sparse} routine. In its basic form, the triplet matrix {\tt T} contains \begin{itemize} \item {\tt T->i} and {\tt T->j}, integer arrays of size {\tt T->nzmax}. \item {\tt T->x}, a {\tt double} or {\tt float} array of size {\tt T->nzmax} or twice that for the complex case. \item {\tt T->z}, a {\tt double} or {\tt float} array of size {\tt T->nzmax} if {\tt T} is zomplex. \end{itemize} The {\tt k}th entry in the data structure has row index {\tt T->i [k]} and column index {\tt T->j [k]}. For a real triplet matrix, its numerical value is {\tt T->x [k]}. For a complex triplet matrix, its real part is {\tt T->x [2*k]} and its imaginary part is {\tt T->x [2*k+1]}. For a zomplex matrix, the real part is {\tt T->x [k]} and imaginary part is {\tt T->z [k]}. The entries can be in any order, and duplicates are permitted. See Section~\ref{cholmod_triplet} for more details. \end{enumerate} Each of the five objects has a routine in CHOLMOD to create and destroy it. CHOLMOD provides many other operations on these objects as well. A few of the most important ones are illustrated in the sample program in the next section. %------------------------------------------------------------------------------- \newpage \section{Simple example program} %------------------------------------------------------------------------------- \input{_simple.tex} The {\tt Demo/cholmod\_*\_simple.c} programs illustrate the basic usage of CHOLMOD. Each of them reads a triplet matrix from a file (in Matrix Market format), convert it into a sparse matrix, creates a linear system, solves it, and prints the norm of the residual. See the {\tt CHOLMOD/Demo/cholmod\_*\_demo.c} program for a more elaborate example. These two sets of programs come in four variants: \begin{itemize} \item di: {\tt double} values, {\tt int32\_t} integers. \item dl: {\tt double} values, {\tt int64\_t} integers. \item si: {\tt float} values, {\tt int32\_t} integers. \item sl: {\tt float} values, {\tt int64\_t} integers. \end{itemize} %------------------------------------------------------------------------------- \newpage \section{Installation of the C-callable library} \label{Install} %------------------------------------------------------------------------------- CHOLMOD requires a suite of external packages, many of which are distributed along with CHOLMOD, but three of which are not. Those included with CHOLMOD are: \begin{itemize} \item AMD: an approximate minimum degree ordering algorithm, by Tim Davis, Patrick Amestoy, and Iain Duff \cite{AmestoyDavisDuff96,AmestoyDavisDuff03}. \item COLAMD: an approximate column minimum degree ordering algorithm, by Tim Davis, Stefan Larimore, John Gilbert, and Esmond Ng \cite{DavisGilbertLarimoreNg00_algo,DavisGilbertLarimoreNg00}. \item CCOLAMD: a constrained approximate column minimum degree ordering algorithm, by Tim Davis and Siva Rajamanickam, based directly on COLAMD. This package is not required if CHOLMOD is compiled with the {\tt -DNCAMD} flag. \item CAMD: a constrained approximate minimum degree ordering algorithm, by Tim Davis and Yanqing Chen, based directly on AMD. This package is not required if CHOLMOD is compiled with the {\tt -DNCAMD} flag. \item {\tt SuiteSparse\_config}: a single place where all sparse matrix packages authored or co-authored by Davis are configured. \item {\tt METIS 5.1.0}: a graph partitioning package by George Karypis, Univ. of Minnesota. A slightly revised copy appears in {\tt CHOLMOD/SuiteSparse\_metis}, but with a revised namespace so that no METIS functions in CHOLMOD conflict with the unmodified METIS. SuiteSparse cannot use any other METIS library except for {\tt CHOLMOD/SuiteSparse\_metis}. There is no conflict with the unmodified METIS, so it can be linked into the user's application alongside {\tt CHOLMOD/SuiteSparse\_metis}. This folder containing the modified METIS is not needed if {\tt -DNPARTITION} is used. See http://www-users.cs.umn.edu/$\sim$karypis/metis for the original version of METIS. \end{itemize} Three other packages are required for optimal performance: \begin{itemize} \item BLAS: the Basic Linear Algebra Subprograms. Not needed if {\tt -DNSUPERNODAL} is used. See http://www.netlib.org for the reference BLAS (not meant for production use). I recommend the Intel MKL BLAS. \item LAPACK: the Basic Linear Algebra Subprograms. Not needed if {\tt -DNSUPERNODAL} is used. See http://www.netlib.org. \item CUDA BLAS: CHOLMOD can exploit an NVIDIA GPU by using the CUDA BLAS for large supernodes. \end{itemize} You must first obtain and install LAPACK, and the BLAS. \noindent CHOLMOD's specific settings are revised by the following compile-time flags for the compiler: \begin{itemize} \item {\tt -DNCHECK}: do not include the Check module. \item {\tt -DNCHOLESKY}: do not include the Cholesky module. \item {\tt -DNPARTITION}: do not include the interface to METIS in the Partition module. \item {\tt -DNCAMD}: do not include the interfaces to CAMD, CCOLAMD, and CSYMAMD in the Partition module. \item {\tt -DNMATRIXOPS}: do not include the MatrixOps module. Note that the Demo requires the MatrixOps module. \item {\tt -DNMODIFY}: do not include the Modify module. \item {\tt -DNSUPERNODAL}: do not include the Supernodal module. \item {\tt -DNPRINT}: do not print anything. \end{itemize} These settings are controlled in cmake by the following variables, which are all \verb'ON' by default: \begin{itemize} \item \verb'CHOLMOD_CHECK': if \verb'OFF': do not use the Check module. \item \verb'CHOLMOD_CHOLESKY': if \verb'OFF': do not use the Cholesky module. \item \verb'CHOLMOD_PARTITION': if \verb'OFF': do not use the interface to METIS in the Partition module. \item \verb'CHOLMOD_CAMD': if \verb'OFF': do not use the interfaces to CAMD, CCOLAMD, and CSYMAMD in the Partition module. \item \verb'CHOLMOD_MATRIXOPS': if \verb'OFF': do not use the MatrixOps module. \item \verb'CHOLMOD_MODIFY': if \verb'OFF': do not use the Modify module. \item \verb'CHOLMOD_SUPERNODAL': if \verb'OFF': do not use the Supernodal module. \item \verb'CHOLMOD_GPL': if \verb'OFF': do not use any GPL-licensed module (MatrixOps, Modify, Supernodal, and GPU-module). \end{itemize} SuiteSparse now has a complete \verb'cmake'-based build system. Each package (SuiteSparse\_congig, AMD, CAMD, CCOLAMD, CAMD, and CHOLMOD) has its own \verb'CMakeLists.txt'. Use \verb'cmake' to build each package in that order. Alternatively, you can use a single top-level \verb'CMakeLists.txt' file to build all packages in SuiteSparse. An optional \verb'Makefile' is provided at the top-level of \verb'SuiteSparse' Type {\tt make} in that directory. The AMD, COLAMD, CAMD, CCOLAMD, and {\tt CHOLMOD} libraries will be compiled. To compile and run demo programs for each package, type \verb'make demos'. For CHOLMOD, the residuals should all be small. CHOLMOD is now ready for use in your own applications. You must link your programs with the {\tt libcholmod.*}, {\tt libamd.*}, {\tt libcolamd.*}, LAPACK, and BLAS libraries. Unless {\tt -DNCAMD} is present at compile time, you must link with {\tt CAMD/libcamd.*}, and {\tt CCOLAMD/libccolamd.*}. Each library has its own \verb'*Config.cmake' script to use in the \verb'cmake' \verb'find_package' command. To install CHOLMOD in default locations use {\tt make install}. To remove CHOLMOD, do {\tt make uninstall}. %------------------------------------------------------------------------------- \newpage \section{Using CHOLMOD in MATLAB} %------------------------------------------------------------------------------- CHOLMOD includes a set of m-files and mexFunctions in the CHOLMOD/MATLAB directory. The following functions are provided: \vspace{0.1in} \begin{tabular}{ll} \hline {\tt analyze} & order and analyze a matrix \\ {\tt bisect} & find a node separator \\ {\tt chol2} & same as {\tt chol} \\ {\tt cholmod2} & same as \verb'x=A\b' \verb'A' is symmetric positive definite \\ {\tt cholmod\_demo} & a short demo program \\ {\tt cholmod\_make} & compiles CHOLMOD for use in MATLAB \\ {\tt etree2} & same as {\tt etree} \\ {\tt graph\_demo} & graph partitioning demo \\ {\tt lchol} & {\tt L*L'} factorization \\ {\tt ldlchol} & {\tt L*D*L'} factorization \\ {\tt ldl\_normest} & estimate {\tt norm(A-L*D*L')} \\ {\tt ldlsolve} & \verb"x = L'\ (D \(L \ b))" \\ {\tt ldlsplit} & split the output of {\tt ldlchol} into {\tt L} and {\tt D} \\ {\tt ldlupdate} & update/downdate an {\tt L*D*L'} factorization \\ {\tt ldlrowmod} & add/delete a row from an {\tt L*D*L'} factorization \\ {\tt metis} & interface to {\tt METIS\_NodeND} ordering \\ {\tt mread} & read a sparse or dense Matrix Market file \\ {\tt mwrite} & write a sparse or dense Matrix Market file \\ {\tt nesdis} & CHOLMOD's nested dissection ordering \\ {\tt resymbol} & recomputes the symbolic factorization \\ {\tt sdmult} & {\tt S*F} where {\tt S} is sparse and {\tt F} is dense \\ {\tt spsym} & determine symmetry \\ {\tt symbfact2} & same as {\tt symbfact} \\ \hline \end{tabular} \vspace{0.1in}\noindent Each function is described in the next sections. \subsection{{\tt analyze}: order and analyze} \input{_analyze_m.tex} \subsection{{\tt bisect}: find a node separator} \input{_bisect_m.tex} \subsection{{\tt chol2}: same as {\tt chol}} \input{_chol2_m.tex} \subsection{{\tt cholmod2}: supernodal backslash} \input{_cholmod2_m.tex} \subsection{{\tt cholmod\_demo}: a short demo program} \input{_cholmod_demo_m.tex} \subsection{{\tt cholmod\_make}: compile CHOLMOD in MATLAB} \input{_cholmod_make_m.tex} \subsection{{\tt etree2}: same as {\tt etree}} \input{_etree2_m.tex} \subsection{{\tt graph\_demo}: graph partitioning demo} \input{_graph_demo_m.tex} \subsection{{\tt lchol}: $\m{LL}\tr$ factorization} \input{_lchol_m.tex} \subsection{{\tt ldlchol}: $\m{LDL}\tr$ factorization} \input{_ldlchol_m.tex} \subsection{{\tt ldlsolve}: solve using an $\m{LDL}\tr$ factorization} \input{_ldlsolve_m.tex} \subsection{{\tt ldlsplit}: split an $\m{LDL}\tr$ factorization} \input{_ldlsplit_m.tex} \subsection{{\tt ldlupdate}: update/downdate an $\m{LDL}\tr$ factorization} \input{_ldlupdate_m.tex} \subsection{{\tt ldlrowmod}: add/delete a row from an $\m{LDL}\tr$ factorization} \input{_ldlrowmod_m.tex} \subsection{{\tt mread}: read a sparse or dense matrix from a Matrix Market file} \input{_mread_m.tex} \subsection{{\tt mwrite}: write a sparse or dense matrix to a Matrix Market file} \input{_mwrite_m.tex} \subsection{{\tt metis}: order with METIS} \input{_metis_m.tex} \subsection{{\tt nesdis}: order with CHOLMOD nested dissection} \input{_nesdis_m.tex} \subsection{{\tt resymbol}: re-do symbolic factorization} \input{_resymbol_m.tex} \subsection{{\tt sdmult}: sparse matrix times dense matrix} \input{_sdmult_m.tex} \subsection{{\tt spsym}: determine symmetry} \input{_spsym_m.tex} \subsection{{\tt symbfact2}: same as {\tt symbfact}} \input{_symbfact2_m.tex} %------------------------------------------------------------------------------- \newpage \section{Installation for use in MATLAB} %------------------------------------------------------------------------------- %------------------------------------------------------------------------------- \subsection{{\tt cholmod\_make}: compiling CHOLMOD in MATLAB} %------------------------------------------------------------------------------- Start MATLAB, {\tt cd} to the {\tt CHOLMOD/MATLAB} directory, and type {\tt cholmod\_make} in the MATLAB command window. This will compile the MATLAB interfaces for METIS and CHOLMOD. %------------------------------------------------------------------------------- \section{Using CHOLMOD with OpenMP acceleration} %------------------------------------------------------------------------------- CHOLMOD includes OpenMP acceleration for some operations. In CHOLMOD versions prior to v6.0.0, the number of threads to use was controlled by a compile time parameter. This is now replaced with run-time controls. \verb'Common->nthreads_max' defaults to \verb'omp_get_max_threads()', or 1 if OpenMP is not in use. This value controls the maximum number of threads that CHOLMOD will use. If zero or less, the default is used. The \verb'Common->chunk' parameter controls how many threads are used when the work to do is low. If $w$ is a count of operations to perform, $c$ = \verb'Common->chunk', and $m$ = \verb'Common->nthreads_max', then a parallel region will use $\max (1, \min (\lfloor w/c \rfloor, m))$ threads. These parameters can be revised by the user application at run time. %------------------------------------------------------------------------------- \section{Using CHOLMOD with GPU acceleration} %------------------------------------------------------------------------------- Starting with CHOLMOD v2.0.0, it is possible to accelerate the numerical factorization phase of CHOLMOD using NVIDIA GPUs. Due to the large computational capability of the GPUs, enabling this capability can result in significant performance improvements. Similar to CPU processing, the GPU is better able to accelerate the dense math associated with larger supernodes. Hence the GPU will provide more significant performance improvements for larger matrices that have more, larger supernodes. In CHOLMOD v2.3.0 this GPU capability has been improved to provide a significant increase in performance and the interface has been expanded to make the use of GPUs more flexible. CHOLMOD can take advantage of a single NVIDIA GPU that supports CUDA and has at least 64MB of memory. (But substantially more memory, typically about 3 GB, is recommended for best performance.) Only the ({\tt double}, {\tt int64\_t}) version of CHOLMOD can leverage GPU acceleration (both real and complex). %------------------------------------------------------------------------------- \subsection{Compiling CHOLMOD with GPU support} %------------------------------------------------------------------------------- In order to support GPU processing, CHOLMOD must be compiled with the preprocessor macro \verb'CHOLMOD_HAS_CUDA' defined. It is enabled by default in {\tt cmake} if you have a GPU, but this can be disabled by setting this to false when using cmake, via the cmake variables \verb'CHOLMOD_USE_CUDA' or \verb'SUITESPARSE_USE_CUDA'. %------------------------------------------------------------------------------- \subsection{Enabling GPU acceleration in CHOLMOD} %------------------------------------------------------------------------------- Even if compiled with GPU support, in CHOLMOD v.2.3.0, GPU processing is not enabled by default and must be specifically requested. There are two ways to do this, either in the code calling CHOLMOD or using environment variables. The code author can specify the use of GPU processing with the {\tt Common->useGPU} variable. If this is set to {\tt 1}, CHOLMOD will attempt to use the GPU. If this is set to {\tt 0} the use of the GPU will be prohibited. If this is set to {\tt -1}, which is the default case, then the environment variables (following paragraph) will be queried to determine if the GPU is to be used. Note that the default value of {\tt -1} is set when {\tt cholmod\_start(Common)} is called, so the code author must set {\tt Common->useGPU} after calling {\tt cholmod\_start}. Alternatively, or if it is not possible to modify the code calling CHOLMOD, GPU processing can invoked using the {\tt CHOLMOD\_USE\_GPU} environment variable. This makes it possible for any CHOLMOD user to invoke GPU processing even if the author of the calling program did not consider this. The interpretation of the environment variable {\tt CHOLMOD\_USE\_GPU} is that if the string evaluates to an integer other than zero, GPU processing will be enabled. Note that the setting of {\tt Common->useGPU} takes precedence and the environment variable {\tt CHOLMOD\_USE\_GPU} will only be queried if {\tt Common->useGPU = -1}. Note that in either case, if GPU processing is requested, but there is no GPU present, CHOLMOD will continue using the CPU only. Consequently it is always safe to request GPU processing. %------------------------------------------------------------------------------- \subsection{Adjustable parameters} %------------------------------------------------------------------------------- There are a number of parameters that have been added to CHOLMOD to control GPU processing. All of these have appropriate defaults such that GPU processing can be used without any modification. However, for any particular combination of CPU/GPU, better performance might be obtained by adjusting these parameters. \bigskip From {\tt t\_cholmod\_gpu.c} \begin{quote} {\tt CHOLMOD\_ND\_ROW\_LIMIT} : Minimum number of rows required in a descendant supernode to be eligible for GPU processing during supernode assembly {\tt CHOLMOD\_ND\_COL\_LIMIT} : Minimum number of columns in a descendant supernode to be eligible for GPU processing during supernode assembly {\tt CHOLMOD\_POTRF\_LIMIT} : Minimum number of columns in a supernode to be eligible for {\tt POTRF} and {\tt TRSM} processing on the GPU {\tt CHOLMOD\_GPU\_SKIP} : Number of small descendant supernodes to assembled on the CPU before querying if the GPU is needs more descendant supernodes queued. \end{quote} From {\tt cholmod\_core.h} \begin{quote} {\tt CHOLMOD\_HOST\_SUPERNODE\_BUFFERS} : Number of buffers in which to queue descendant supernodes for GPU processing \end{quote} Programatically \begin{quote} {\tt Common->maxGpuMemBytes} : Specifies the maximum amount of memory, in bytes, that CHOLMOD can allocate on the GPU. If this parameter is not set, CHOLMOD will allocate as much GPU memory as possible. Hence, the purpose of this parameter is to restrict CHOLMOD's GPU memory use so that CHOLMOD can be used simultaneously with other codes that also use GPU acceleration and require some amount of GPU memory. If the specified amount of GPU memory is not allocatable, CHOLMOD will allocate the available memory and continue. {\tt Common->maxGpuMemFraction} : Entirely similar to {\tt Common->maxGpuMemBytes} but with the memory specified as a fraction of total GPU memory. Note that if both {\tt maxGpuMemBytes} and {\tt maxGpuMemFraction} are specified, whichever results in the minimum amount of memory will be used. \end{quote} Environment variables \begin{quote} {\tt CHOLMOD\_GPU\_MEM\_BYTES} : Environment variable with a meaning equivalent to \newline {\tt Common->maxGpuMemBytes}. This will only be queried if {\tt Common->useGPU = -1}. {\tt CHOLMOD\_GPU\_MEM\_FRACTION} : Environment variable with a meaning equivalent to \newline {\tt Common->maxGpuMemFraction}. This will only be queried if {\tt Common->useGPU = -1}. \end{quote} %------------------------------------------------------------------------------- \newpage \section{Integer and floating-point types, and notation used} %------------------------------------------------------------------------------- CHOLMOD supports both {\tt int32\_t} and {\tt int64\_t} integers. CHOLMOD routines with the prefix {\tt cholmod\_} use {\tt int32\_t} integers, {\tt cholmod\_l\_} routines use {\tt int64\_t}. Floating-point values are {\tt double} or {\tt float}, depending on the {\tt A->dtype} field for a sparse matrix, triplet matrix, dense matrix, or factorization object. Two kinds of complex matrices are supported: complex and zomplex. A complex matrix is held in a manner that is compatible with the Fortran and ANSI C99 complex data type. A complex array of size {\tt n} is a {\tt double} or {\tt float} array {\tt x} of size {\tt 2*n}, with the real and imaginary parts interleaved, with the real part comes first, as a {\tt double} or {\tt float} followed the imaginary part, also as a {\tt double} or {\tt float}. Thus, the real part of the {\tt k}th entry is {\tt x[2*k]} and the imaginary part is {\tt x[2*k+1]}. A zomplex matrix of size {\tt n} stores its real part in one {\tt double} or {\tt float} array of size {\tt n} called {\tt x} and its imaginary part in another {\tt double} or {\tt float} array of size {\tt n} called {\tt z} (thus the name ``zomplex''). This also how MATLAB stored its complex matrices in R2017b and earlier. The real part of the {\tt k}th entry is {\tt x[k]} and the imaginary part is {\tt z[k]}. In MATLAB R2018a, complex matrices are stored in the standard interleaved format. The CHOLMOD MATLAB interface uses this, and thus requires MATLAB R2018a or later. Unlike {\tt UMFPACK}, the same routine name in CHOLMOD is used for pattern-only, real, complex, and zomplex matrices, and also for both {\tt double} and {\tt float} values. For example, the statement \begin{verbatim} C = cholmod_copy_sparse (A, &Common) ; \end{verbatim} creates a copy of a pattern, real, complex, or zomplex sparse matrix {\tt A}. The xtype (pattern, real, complex, or zomplex) of the resulting sparse matrix {\tt C} is the same as {\tt A} (a pattern-only sparse matrix contains no floating-point values). In the above case, {\tt C} and {\tt A} use {\tt int32\_t} integers. For {\tt int64\_t} integers, the statement would become: \begin{verbatim} C = cholmod_l_copy_sparse (A, &Common) ; \end{verbatim} The last parameter of all CHOLMOD routines is always {\tt \&Common}, a pointer to the {\tt cholmod\_common} object, which contains parameters, statistics, and workspace used throughout CHOLMOD. The {\tt xtype} of a CHOLMOD object (sparse matrix, triplet matrix, dense matrix, or factorization) determines whether it is pattern-only, real, complex, or zomplex. The {\tt dtype} of a CHOLMOD object (sparse matrix, triplet matrix, dense matrix, or factorization) determines whether it is {\tt double} or {\tt float}. These two terms are often added together when passing parameters to CHOLMOD, as {\tt xtype + dtype}. This API design was chosen for backward compatibility with CHOLMOD 4.x and earlier. The names of the {\tt int32\_t} versions are primarily used in this document. To obtain the name of the {\tt int64\_t} version of the same routine, simply replace {\tt cholmod\_} with {\tt cholmod\_l\_}. MATLAB matrix notation is used throughout this document and in the comments in the CHOLMOD code itself. If you are not familiar with MATLAB, here is a short introduction to the notation, and a few minor variations used in CHOLMOD: \begin{itemize} \item {\tt C=A+B} and {\tt C=A*B}, respectively are a matrix add and multiply if both {\tt A} and {\tt B} are matrices of appropriate size. If {\tt A} is a scalar, then it is added to or multiplied with every entry in {\tt B}. \item {\tt a:b} where {\tt a} and {\tt b} are integers refers to the sequence {\tt a}, {\tt a+1}, ... {\tt b}. \item {\tt [A B]} and {\tt [A,B]} are the horizontal concatenation of {\tt A} and {\tt B}. \item {\tt [A;B]} is the vertical concatenation of {\tt A} and {\tt B}. \item {\tt A(i,j)} can refer either to a scalar or a submatrix. For example: \newline \vspace{0.05in} \begin{tabular}{ll} \hline {\tt A(1,1)} & a scalar. \\ {\tt A(:,j)} & column {\tt j} of {\tt A}. \\ {\tt A(i,:)} & row {\tt i} of {\tt A}. \\ {\tt A([1 2], [1 2])} & a 2-by-2 matrix containing the 2-by-2 leading minor of {\tt A}. \\ \hline \end{tabular} \newline \vspace{0.1in} If {\tt p} is a permutation of {\tt 1:n}, and {\tt A} is {\tt n}-by-{\tt n}, then {\tt A(p,p)} corresponds to the permuted matrix $\m{PAP}\tr$. \item {\tt tril(A)} is the lower triangular part of {\tt A}, including the diagonal. \item {\tt tril(A,k)} is the lower triangular part of {\tt A}, including entries on and below the $k$th diagonal. \item {\tt triu(A)} is the upper triangular part of {\tt A}, including the diagonal. \item {\tt triu(A,k)} is the upper triangular part of {\tt A}, including entries on and above the $k$th diagonal. \item {\tt size(A)} returns the dimensions of {\tt A}. \item {\tt find(x)} if {\tt x} is a vector returns a list of indices {\tt i} for which {\tt x(i)} is nonzero. \item {\tt A'} is the transpose of {\tt A} if {\tt A} is real, or the complex conjugate transpose if {\tt A} is complex. \item {\tt A.'} is the array transpose of {\tt A}. \item {\tt diag(A)} is the diagonal of {\tt A} if {\tt A} is a matrix. \item {\tt C=diag(s)} is a diagonal matrix if {\tt s} is a vector, with the values of {\tt s} on the diagonal of {\tt C}. \item {\tt S=spones(A)} returns a binary matrix {\tt S} with the same nonzero pattern of {\tt A}. \item {\tt nnz(A)} is the number of nonzero entries in {\tt A}. \end{itemize} \noindent Variations to MATLAB notation used in this document: \begin{itemize} \item CHOLMOD uses 0-based notation (the first entry in the matrix is {\tt A(0,0)}). MATLAB is 1-based. The context is usually clear. \item {\tt I} is the identity matrix. \item {\tt A(:,f)}, where {\tt f} is a set of columns, is interpreted differently in CHOLMOD, but just for the set named {\tt f}. See {\tt cholmod\_transpose\_unsym} for details. \end{itemize} %------------------------------------------------------------------------------- \newpage \section{The CHOLMOD Modules, objects, and functions} \label{Modules} %------------------------------------------------------------------------------- CHOLMOD contains over 150 {\tt int32\_t}-based routines and the same number of {\tt int64\_t} routines with the same name except for {\tt \_l\_} added. These are divided into a set of inter-related Modules. Each Module contains a set of related functions. The functions are divided into two types: Primary and Secondary, to reflect how a user will typically use CHOLMOD. Most users will find the Primary routines to be sufficient to use CHOLMOD in their programs. Each Module exists as a sub-directory (a folder for Windows users) within the CHOLMOD directory (or folder). \vspace{0.1in} \noindent There are seven Modules that provide user-callable routines for CHOLMOD. \begin{enumerate} \item {\tt Utility}: basic data structures and definitions \item {\tt Check}: prints/checks each of CHOLMOD's objects \item {\tt Cholesky}: sparse Cholesky factorization \item {\tt Modify}: sparse Cholesky update/downdate and row-add/row-delete \item {\tt MatrixOps}: sparse matrix operators (add, multiply, norm, scale) \item {\tt Supernodal}: supernodal sparse Cholesky factorization \item {\tt Partition}: graph-partitioning-based orderings, which uses a slightly modified copy of METIS 5.1.0 in the \verb'SuiteSparse_metis' folder. \end{enumerate} \noindent Additional directories provide support functions and documentation: \begin{enumerate} \item {\tt Include}: include files for CHOLMOD and programs that use CHOLMOD \item {\tt Demo}: simple programs that illustrate the use of CHOLMOD \item {\tt Doc}: documentation (including this document) \item {\tt MATLAB}: CHOLMOD's interface to MATLAB \item {\tt Tcov}: an exhaustive test coverage (requires Linux or Solaris) \item \verb'cmake_modules': how other packages can find CHOLMOD when using cmake. \item \verb'Config': a folder containing the input files to create the \verb'cholmod.h' include file, via cmake. \end{enumerate} %------------------------------------------------------------------------------- \subsection{CHOLMOD objects} %------------------------------------------------------------------------------- A CHOLMOD sparse, dense, or triplet matrix A, or a sparse factorization L can hold numeric values of 8 different types, according to its {\tt A->xtype} and {\tt A->dtype} parameters (or {\tt L->xtype} and {\tt L->dtype} for a sparse factor object). These values are held in the {\tt A->x} array, and also {\tt A->z} for zomplex matrices. {\bf xtype:} the matrix is real, complex, "zomplex", or pattern-only. \begin{itemize} \item (0): \verb'CHOLMOD_PATTERN': \verb'A->x' and \verb'A->z' are \verb'NULL'. The matrix has no numerical values. Only the pattern is stored. \item (1): \verb'CHOLMOD_REAL': The matrix is real, and the values are held in \verb'A->x', whose size (in terms of double or float values) is given by \verb'A->nzmax'. The kth value in the matrix is held in \verb'A->x[k]'. \item (2): \verb'CHOLMOD_COMPLEX': The matrix is complex, with interleaved real and imaginary parts. The kth value in the matrix is held in \verb'A->x[2*k]' and \verb'A->x[2*k+1]', where \verb'A->x' can hold up to \verb'2*A->nzmax' values. \item (3): \verb'CHOLMOD_ZOMPLEX': The matrix is complex, with separate array for the real and imaginary parts. The kth value in the matrix is held in \verb'A->x[k]', and \verb'A->z[k]', where \verb'A->x' and \verb'A->z' can hold up to A->nzmax values each. \end{itemize} {\bf dtype}: this parameter determines the type of values in A->x (and A->z if zomplex). \begin{itemize} \item (0) \verb'CHOLMOD_DOUBLE': \verb'A->x' and \verb'A->z' (for zomplex matrices) are \verb'double'. If A is real, \verb'A->x' has a size of \verb'A->nzmax * sizeof (double)' bytes. If A is complex, \verb'A->x' has size \verb'A->nzmax * 2 * sizeof (double)'. If zomplex, both \verb'A->x' and \verb'A->z' have size \verb'A->nzmax * sizeof (double)'. \item (4) \verb'CHOLMOD_SINGLE': \verb'A->x' and \verb'A->z' (for zomplex matrices) are \verb'float'. If A is real, \verb'A->x' has a size of \verb'A->nzmax * sizeof (float)'. If A is complex, \verb'A->x' has \verb'size A->nzmax * 2 * sizeof (float)'. If zomplex, both \verb'A->x' and \verb'A->z' have size \verb'A->nzmax * sizeof (float)'. This feature is new to CHOLMOD v5. \end{itemize} Unless stated otherwise, the xtype and dtypes of all inputs to a method must be the same. Many methods accept an xdtype parameter, which is simply xtype + dtype, combining the two parameters into a single number handling all 8 cases: \begin{itemize} \item (0) \verb'CHOLMOD_DOUBLE' + \verb'CHOLMOD_PATTERN': a pattern-only matrix \item (1) \verb'CHOLMOD_DOUBLE' + \verb'CHOLMOD_REAL': a double real matrix \item (2) \verb'CHOLMOD_DOUBLE' + \verb'CHOLMOD_COMPLEX': a double complex matrix \item (3) \verb'CHOLMOD_DOUBLE' + \verb'CHOLMOD_ZOMPLEX': a double zomplex matrix \item (4) \verb'CHOLMOD_SINGLE' + \verb'CHOLMOD_PATTERN': a pattern-only matrix \item (5) \verb'CHOLMOD_SINGLE' + \verb'CHOLMOD_REAL': a float real matrix \item (6) \verb'CHOLMOD_SINGLE' + \verb'CHOLMOD_COMPLEX': a float complex matrix \item (7) \verb'CHOLMOD_SINGLE' + \verb'CHOLMOD_ZOMPLEX': a float zomplex matrix \end{itemize} This approach was selected for backward compatibility with CHOLMOD v4 and earlier, where only the first four values were supported, and where the parameter was called \verb'xtype' instead of \verb'xdtype'. Several function names reflect the older parameter name (\verb'cholmod_*_xtype'), but they have not been renamed \verb"_xdtype", for backward compatibility. A CHOLMOD sparse or triplet matrix A can held in three symmetry formats according to its \verb'A->stype' parameter. Dense matrices do not have this parameter and are always treated as unsymmetric. A sparse factor object L is always held in lower triangular form, with no entries ever held in the strictly upper triangular part. \begin{itemize} \item 0: the matrix is unsymmetric with both lower and upper parts stored. \item $<0$: the matrix is symmetric, with just the lower triangular part and diagonal stored. Any entries in the upper part are ignored. \item $>0$: the matrix is symmetric, with just the upper triangular part stored and diagonal. Any entries in the upper part are ignored. \end{itemize} If a sparse or triplet matrix A is complex or zomplex, most methods treat the matrix as Hermitian, where A(i,j) is the complex conjugate of A(j,i), when i is not equal to j. Some methods can also interpret the matrix as complex symmetric, where A(i,j) == A(j,i) when i != j. This is not determined by the matrix itself, but by a "mode" parameter of the function. This mode parameter also determines if the values of any matrix are to be ignored entirely, in which case only the pattern is operated on. Any output matrix will have an xtype of \verb'CHOLMOD_PATTERN'. The valid mode values are given below, except that many methods do not handle the negative cases. Values below the range accepted by the method are treated as its lowest accepted value, and values above the range accepted by the method are treated as its highest accepted value. \begin{itemize} \item mode = 2: the numerical values of a real, complex, or zomplex matrix are handled. If the matrix is complex or zomplex, an entry A(i,j) that not stored (or in the ignored part) is treated as the complex conjugate of A (j,i). Use this mode to treat a complex or zomplex matrix as Hermitian. \item mode = 1: the numerical values of a real, complex, or zomplex matrix are handled. If the matrix is complex or zomplex, an entry A(i,j) that not stored (or in the ignored part) is treated as equal A (j,i). Use this mode to treat a complex or zomplex matrix as complex symmetric. \item mode = 0: the numerical values are ignored. Any output matrix will have an xtype of \verb'CHOLMOD_PATTERN'. This mode allows inputs to have different dtypes. \item mode = -1: the same as mode = 0, except that the diagonal entries are ignored, and do not appear in any output matrix. \item mode = -2: the same as mode = -1, except that the output matrix is given an additional slack space so that it can hold about 50% more entries. This mode is documented here but it is primarily meant for internal use, for CHOLMOD's interface to the AMD, CAMD, COLAMD, and CCOLAMD ordering methods. \end{itemize} The integer arrays in all objects are either int32 or int64, as determined by \verb'A->type'. This integer type must be identical for all inputs, and must also match both the function name (\verb'cholmod_method' for int32, or \verb'cholmod_l_method' for int64) and the \verb'Common->itype' as defined when CHOLMOD was initialized (via \verb'cholmod_start' for int32, or \verb'cholmod_l_start' for int64). %------------------------------------------------------------------------------- \subsection{{\tt Utility} Module: basic data structures and definitions} %------------------------------------------------------------------------------- CHOLMOD includes five basic objects, defined in the {\tt Utility} Module. The {\tt Utility Module} provides basic operations for these objects and is required by all six other CHOLMOD library Modules: \subsubsection{{\tt cholmod\_common}: parameters, statistics, and workspace} You must call {\tt cholmod\_start} before calling any other CHOLMOD routine, and you must call {\tt cholmod\_finish} as your last call to CHOLMOD (with the exception of {\tt cholmod\_print\_common} and {\tt cholmod\_check\_common} in the {\tt Check} Module). Once the {\tt cholmod\_common} object is initialized, the user may modify CHOLMOD's parameters held in this object, and obtain statistics on CHOLMOD's activity. When using 64-bit integers, use {\tt cholmod\_l\_start} and {\tt cholmod\_l\_finish} instead. Matrices and other objects from different integer sizes cannot be mixed \vspace{0.1in} \noindent Primary routines for the {\tt cholmod\_common} object: % 2 \begin{itemize} \item {\tt cholmod\_start}: the first call to CHOLMOD. \item {\tt cholmod\_finish}: the last call to CHOLMOD (frees workspace in the {\tt cholmod\_common} object). \end{itemize} \noindent Secondary routines for the {\tt cholmod\_common} object: % 11 \begin{itemize} \item {\tt cholmod\_defaults}: restores default parameters \item {\tt cholmod\_maxrank}: determine maximum rank for update/downdate. \item {\tt cholmod\_allocate\_work}: allocate workspace ({\tt double} only). \item {\tt cholmod\_alloc\_work}: allocate workspace, {\tt double} or {\tt float}. \item {\tt cholmod\_free\_work}: free workspace. \item {\tt cholmod\_clear\_flag}: clear {\tt Flag} array. \item {\tt cholmod\_error}: called when CHOLMOD encounters and error. \item {\tt cholmod\_dbound}: bounds the diagonal of $\m{L}$ or $\m{D}$ ({\tt double} case). \item {\tt cholmod\_sbound}: bounds the diagonal of $\m{L}$ or $\m{D}$. ({\tt float} case). \item {\tt cholmod\_hypot}: compute {\tt sqrt(x*x+y*y)} accurately. \item {\tt cholmod\_divcomplex}: complex divide. \end{itemize} %------------------------------------------------------------------------------- \subsubsection{{\tt cholmod\_sparse}: a sparse matrix in compressed column form} %------------------------------------------------------------------------------- A sparse matrix {\tt A} is held in compressed column form. In the basic type (``packed,'' which corresponds to how MATLAB stores its sparse matrices), and {\tt nrow}-by-{\tt ncol} matrix with {\tt nzmax} entries is held in three arrays: {\tt p} of size {\tt ncol+1}, {\tt i} of size {\tt nzmax}, and {\tt x} of size {\tt nzmax}. Row indices of nonzero entries in column {\tt j} are held in {\tt i [p[j] ... p[j+1]-1]}, and their corresponding numerical values are held in {\tt x [p[j] ... p[j+1]-1]}. The first column starts at location zero ({\tt p[0]=0}). There may be no duplicate entries. Row indices in each column may be sorted or unsorted (the {\tt A->sorted} flag must be false if the columns are unsorted). The {\tt A->stype} determines the storage: 0 if the matrix is unsymmetric, 1 if the matrix is symmetric with just the upper triangular part stored, and -1 if the matrix is symmetric with just the lower triangular part stored. In ``unpacked'' form, an additional array {\tt nz} of size {\tt ncol} is used. The end of column {\tt j} in {\tt i} and {\tt x} is given by {\tt p[j]+nz[j]}. Columns not need be in any particular order ({\tt p[0]} need not be zero), and there may be gaps between the columns. \vspace{0.1in} \noindent Primary routines for the {\tt cholmod\_sparse} object: % 2 \begin{itemize} \item {\tt cholmod\_allocate\_sparse}: allocate a sparse matrix \item {\tt cholmod\_free\_sparse}: free a sparse matrix \end{itemize} \noindent Secondary routines for the {\tt cholmod\_sparse} object: % 17 \begin{itemize} \item {\tt cholmod\_reallocate\_sparse}: change the size (number of entries) of a sparse matrix. \item {\tt cholmod\_nnz}: number of nonzeros in a sparse matrix. \item {\tt cholmod\_speye}: sparse identity matrix. \item {\tt cholmod\_spzeros}: sparse zero matrix. \item {\tt cholmod\_transpose}: transpose a sparse matrix. \item {\tt cholmod\_transpose\_unsym}: transpose/permute an unsymmetric sparse matrix. \item {\tt cholmod\_transpose\_sym}: transpose/permute a symmetric sparse matrix. \item {\tt cholmod\_ptranspose}: transpose/permute a sparse matrix. \item {\tt cholmod\_sort}: sort row indices in each column of a sparse matrix. \item {\tt cholmod\_band\_nnz}: number of entries in a band of a sparse matrix. \item {\tt cholmod\_band}: extract a band of a sparse matrix. \item {\tt cholmod\_band\_inplace}: remove entries not with a band. \item {\tt cholmod\_aat}: {\tt C = A*A'}. \item {\tt cholmod\_copy\_sparse}: {\tt C = A}, create an exact copy of a sparse matrix. \item {\tt cholmod\_copy}: {\tt C = A}, with possible change of {\tt stype}. \item {\tt cholmod\_add}: {\tt C = alpha*A + beta*B}. \item {\tt cholmod\_sparse\_xtype}: change the {\tt xtype} and/or {\tt dtype} of a sparse matrix. \end{itemize} %------------------------------------------------------------------------------- \subsubsection{{\tt cholmod\_factor}: a symbolic or numeric factorization} %------------------------------------------------------------------------------- A factor can be in $\m{LL}\tr$ or $\m{LDL}\tr$ form, and either supernodal or simplicial form. In simplicial form, this is very much like a packed or unpacked {\tt cholmod\_sparse} matrix. In supernodal form, adjacent columns with similar nonzero pattern are stored as a single block (a supernode). \vspace{0.1in} \noindent Primary routine for the {\tt cholmod\_factor} object: % 1 \begin{itemize} \item {\tt cholmod\_free\_factor}: free a factor \end{itemize} \noindent Secondary routines for the {\tt cholmod\_factor} object: % 9 \begin{itemize} \item {\tt cholmod\_allocate\_factor}: allocate a factor. ({\tt double} or {\tt float}). You will normally use {\tt cholmod\_analyze} to create a factor. \item {\tt cholmod\_alloc\_factor}: allocate a factor ({\tt double} or {\tt float}). \item {\tt cholmod\_reallocate\_factor}: change the number of entries in a factor. \item {\tt cholmod\_change\_factor}: change the type of a factor ($\m{LDL}\tr$ to $\m{LL}\tr$, supernodal to simplicial, etc.). \item {\tt cholmod\_pack\_factor}: pack the columns of a factor. \item {\tt cholmod\_reallocate\_column}: resize a single column of a factor. \item {\tt cholmod\_factor\_to\_sparse}: create a sparse matrix copy of a factor. \item {\tt cholmod\_copy\_factor}: create a copy of a factor. \item {\tt cholmod\_factor\_xtype}: change the {\tt xtype} and/or {\tt dtype} of a factor. \end{itemize} %------------------------------------------------------------------------------- \subsubsection{{\tt cholmod\_dense}: a dense matrix} %------------------------------------------------------------------------------- This consists of a dense array of numerical values and its dimensions. \vspace{0.1in} \noindent Primary routines for the {\tt cholmod\_dense} object: % 2 \begin{itemize} \item {\tt cholmod\_allocate\_dense}: allocate a dense matrix. \item {\tt cholmod\_free\_dense}: free a dense matrix. \end{itemize} \vspace{0.1in} \noindent Secondary routines for the {\tt cholmod\_dense} object: % 10 \begin{itemize} \item {\tt cholmod\_zeros}: allocate a dense matrix of all zeros. \item {\tt cholmod\_ones}: allocate a dense matrix of all ones. \item {\tt cholmod\_eye}: allocate a dense identity matrix . \item {\tt cholmod\_ensure\_dense}: ensure a dense matrix has a given size and type. \item {\tt cholmod\_sparse\_to\_dense}: create a dense matrix copy of a sparse matrix. \item {\tt cholmod\_dense\_nnz}: number of nonzeros in a dense matrix. \item {\tt cholmod\_dense\_to\_sparse}: create a sparse matrix copy of a dense matrix. \item {\tt cholmod\_copy\_dense}: create a copy of a dense matrix. \item {\tt cholmod\_copy\_dense2}: copy a dense matrix (pre-allocated). \item {\tt cholmod\_dense\_xtype}: change the {\tt xtype} and/or {\tt dtype} of a dense matrix. \end{itemize} %------------------------------------------------------------------------------- \subsubsection{{\tt cholmod\_triplet}: a sparse matrix in ``triplet'' form} %------------------------------------------------------------------------------- The {\tt cholmod\_sparse} matrix is the basic sparse matrix used in CHOLMOD, but it can be difficult for the user to construct. It also does not easily support the inclusion of new entries in the matrix. The {\tt cholmod\_triplet} matrix is provided to address these issues. A sparse matrix in triplet form consists of three arrays of size {\tt nzmax}: {\tt i}, {\tt j}, and {\tt x}, and a {\tt z} array for the zomplex case. \vspace{0.1in} \noindent Primary routines for the {\tt cholmod\_triplet} object: % 3 \begin{itemize} \item {\tt cholmod\_allocate\_triplet}: allocate a triplet matrix. \item {\tt cholmod\_free\_triplet}: free a triplet matrix. \item {\tt cholmod\_triplet\_to\_sparse}: create a sparse matrix copy of a triplet matrix. \end{itemize} \noindent Secondary routines for the {\tt cholmod\_triplet} object: % 4 \begin{itemize} \item {\tt cholmod\_reallocate\_triplet}: change the number of entries in a triplet matrix. \item {\tt cholmod\_sparse\_to\_triplet}: create a triplet matrix copy of a sparse matrix. \item {\tt cholmod\_copy\_triplet}: create a copy of a triplet matrix. \item {\tt cholmod\_triplet\_xtype}: change the {\tt xtype} and/or {\tt dtype} of a triplet matrix. \end{itemize} %------------------------------------------------------------------------------- \subsubsection{Memory management routines} %------------------------------------------------------------------------------- By default, CHOLMOD uses the ANSI C {\tt malloc}, {\tt free}, {\tt calloc}, and {\tt realloc} routines. You may use different routines by modifying function pointers in the {\tt SuiteSparse\_config} package. Refer to the user guide for that package for more details. \vspace{0.1in} \noindent Primary routines: % 2 \begin{itemize} \item {\tt cholmod\_malloc}: {\tt malloc} wrapper. \item {\tt cholmod\_free}: {\tt free} wrapper. \end{itemize} \noindent Secondary routines: % 3 \begin{itemize} \item {\tt cholmod\_calloc}: {\tt calloc} wrapper. \item {\tt cholmod\_realloc}: {\tt realloc} wrapper. \item {\tt cholmod\_realloc\_multiple}: {\tt realloc} wrapper for multiple objects. \end{itemize} %------------------------------------------------------------------------------- \subsubsection{{\tt cholmod\_version:} Version control} %------------------------------------------------------------------------------- The {\tt cholmod\_version} function returns the current version of CHOLMOD. %------------------------------------------------------------------------------- \subsection{{\tt Check} Module: print/check the CHOLMOD objects} %------------------------------------------------------------------------------- The {\tt Check} Module contains routines that check and print the five basic objects in CHOLMOD, and three kinds of integer vectors (a set, a permutation, and a tree). It also provides a routine to read a sparse matrix from a file in Matrix Market format (http://www.nist.gov/MatrixMarket). Requires the {\tt Utility} Module. \vspace{0.1in} \noindent Primary routines: % 5 \begin{itemize} \item {\tt cholmod\_print\_common}: print the {\tt cholmod\_common} object, including statistics on CHOLMOD's behavior (fill-in, flop count, ordering methods used, and so on). \item {\tt cholmod\_write\_sparse}: write a sparse matrix to a file in Matrix Market format. \item {\tt cholmod\_write\_dense}: write a sparse matrix to a file in Matrix Market format. \item {\tt cholmod\_read\_matrix}: read a sparse or dense matrix from a file in Matrix Market format. \item {\tt cholmod\_read\_matrix2}: read a sparse or dense matrix from a file in Matrix Market format ({\tt double} or {\tt float}). \end{itemize} \vspace{0.1in} \noindent Secondary routines: % 19 \begin{itemize} \item {\tt cholmod\_check\_common}: check the {\tt cholmod\_common} object \item {\tt cholmod\_check\_sparse}: check a sparse matrix \item {\tt cholmod\_print\_sparse}: print a sparse matrix \item {\tt cholmod\_check\_dense}: check a dense matrix \item {\tt cholmod\_print\_dense}: print a dense matrix \item {\tt cholmod\_check\_factor}: check a Cholesky factorization \item {\tt cholmod\_print\_factor}: print a Cholesky factorization \item {\tt cholmod\_check\_triplet}: check a triplet matrix \item {\tt cholmod\_print\_triplet}: print a triplet matrix \item {\tt cholmod\_check\_subset}: check a subset (integer vector in given range) \item {\tt cholmod\_print\_subset}: print a subset (integer vector in given range) \item {\tt cholmod\_check\_perm}: check a permutation (an integer vector) \item {\tt cholmod\_print\_perm}: print a permutation (an integer vector) \item {\tt cholmod\_check\_parent}: check an elimination tree (an integer vector) \item {\tt cholmod\_print\_parent}: print an elimination tree (an integer vector) \item {\tt cholmod\_read\_triplet}: read a triplet matrix from a file \item {\tt cholmod\_read\_triplet2}: read a triplet matrix from a file ({\tt double} or {\tt float}) \item {\tt cholmod\_read\_sparse}: read a sparse matrix from a file \item {\tt cholmod\_read\_sparse2}: read a sparse matrix from a file ({\tt double} or {\tt float}) \item {\tt cholmod\_read\_dense}: read a dense matrix from a file \item {\tt cholmod\_read\_dense2}: read a dense matrix from a file ({\tt double} or {\tt float}) % \item {\tt cholmod\_gpu\_stats}: print GPU timing statistics \end{itemize} %------------------------------------------------------------------------------- \subsection{{\tt Cholesky} Module: sparse Cholesky factorization} %------------------------------------------------------------------------------- The primary routines are all that a user requires to order, analyze, and factorize a sparse symmetric positive definite matrix $\m{A}$ (or $\m{AA}\tr$), and to solve $\m{Ax}=\m{b}$ (or $\m{AA}\tr\m{x}=\m{b}$). The primary routines rely on the secondary routines, the {\tt Utility} Module, and the AMD and COLAMD packages. They make optional use of the {\tt Supernodal} and {\tt Partition} Modules, the METIS package, the CAMD package, and the CCOLAMD package. The {\tt Cholesky} Module is required by the {\tt Partition} Module. \vspace{0.1in} \noindent Primary routines: \begin{itemize} \item {\tt cholmod\_analyze}: order and analyze (simplicial or supernodal). \item {\tt cholmod\_factorize}: simplicial or supernodal Cholesky factorization. \item {\tt cholmod\_solve}: solve a linear system (simplicial or supernodal, dense $\m{x}$ and $\m{b}$). \item {\tt cholmod\_spsolve}: solve a linear system (simplicial or supernodal, sparse $\m{x}$ and $\m{b}$ ). \end{itemize} \noindent Secondary routines: \begin{itemize} \item {\tt cholmod\_analyze\_p}: analyze, with user-provided permutation or $\m{f}$ set. % \item {\tt cholmod\_analyze\_p2}: analyze for sparse QR or Cholesky. \item {\tt cholmod\_factorize\_p}: factorize, with user-provided permutation or $\m{f}$. \item {\tt cholmod\_analyze\_ordering}: analyze a permutation \item {\tt cholmod\_solve2}: solve a linear system, reusing workspace. \item {\tt cholmod\_etree}: find the elimination tree. \item {\tt cholmod\_rowcolcounts}: compute the row/column counts of $\m{L}$. \item {\tt cholmod\_amd}: order using AMD. \item {\tt cholmod\_colamd}: order using COLAMD. \item {\tt cholmod\_rowfac}: incremental simplicial factorization. \item {\tt cholmod\_row\_subtree}: find the nonzero pattern of a row of $\m{L}$. \item {\tt cholmod\_lsolve\_pattern}: find the nonzero pattern of $\m{L}^{-1}b$. \item {\tt cholmod\_row\_lsubtree}: find the nonzero pattern of a row of $\m{L}$. \item {\tt cholmod\_resymbol}: recompute the symbolic pattern of $\m{L}$. \item {\tt cholmod\_resymbol\_noperm}: recompute the symbolic pattern of $\m{L}$, no permutation. \item {\tt cholmod\_rcond}: compute the reciprocal condition number \item {\tt cholmod\_postorder}: postorder a tree. estimate. % \item {\tt cholmod\_rowfac\_mask}: for use in LPDASA only. \end{itemize} %------------------------------------------------------------------------------- \subsection{{\tt Modify} Module: update/downdate a sparse Cholesky factorization} %------------------------------------------------------------------------------- The {\tt Modify} Module contains sparse Cholesky modification routines: update, downdate, row-add, and row-delete. It can also modify a corresponding solution to $\m{Lx}=\m{b}$ when L is modified. This module is most useful when applied on a Cholesky factorization computed by the {\tt Cholesky} module, but it does not actually require the {\tt Cholesky} module. The {\tt Utility} module can create an identity Cholesky factorization ($\m{LDL}\tr$ where $\m{L}=\m{D}=\m{I}$) that can then be modified by these routines. Requires the {\tt Utility} module. Not required by any other CHOLMOD Module. \vspace{0.1in} \noindent Primary routine: \begin{itemize} \item {\tt cholmod\_updown}: multiple rank update/downdate \end{itemize} \noindent Secondary routines: \begin{itemize} \item {\tt cholmod\_updown\_solve}: update/downdate, and modify solution to $\m{Lx=b}$ % \item {\tt cholmod\_updown\_mark}: update/downdate, and modify solution to % partial $\m{Lx=b}$ % \item {\tt cholmod\_updown\_mask}: for use in LPDASA only. \item {\tt cholmod\_rowadd}: add a row to an $\m{LDL}\tr$ factorization \item {\tt cholmod\_rowadd\_solve}: add a row, and update solution to $\m{Lx=b}$ % \item {\tt cholmod\_rowadd\_mark}: add a row, and update solution to % partial $\m{Lx=b}$ \item {\tt cholmod\_rowdel}: delete a row from an $\m{LDL}\tr$ factorization \item {\tt cholmod\_rowdel\_solve}: delete a row, and downdate $\m{Lx=b}$ % \item {\tt cholmod\_rowdel\_mark}: delete a row, and downdate solution to % partial $\m{Lx=b}$ \end{itemize} %------------------------------------------------------------------------------- \subsection{{\tt MatrixOps} Module: basic sparse matrix operations} %------------------------------------------------------------------------------- The {\tt MatrixOps} Module provides basic operations on sparse and dense matrices. Requires the {\tt Utility} module. Not required by any other CHOLMOD module. In the descriptions below, {\tt A}, {\tt B}, and {\tt C:} are sparse matrices ({\tt cholmod\_sparse}), {\tt X} and {\tt Y} are dense matrices ({\tt cholmod\_dense}), {\tt s} is a scalar or vector, and {\tt alpha} {\tt beta} are scalars. Many of these operations are also available in GraphBLAS, with better performance. \begin{itemize} \item {\tt cholmod\_drop}: drop entries from A with absolute value $\ge$ a given tolerance. \item {\tt cholmod\_norm\_dense}: {\tt s = norm (X)}, 1-norm, infinity-norm, or 2-norm \item {\tt cholmod\_norm\_sparse}: {\tt s = norm (A)}, 1-norm or infinity-norm \item {\tt cholmod\_scale}: {\tt A = diag(s)*A}, {\tt A*diag(s)}, {\tt s*A} or {\tt diag(s)*A*diag(s)}. \item {\tt cholmod\_sdmult}: {\tt Y = alpha*(A*X) + beta*Y} or {\tt alpha*(A'*X) + beta*Y}. \item {\tt cholmod\_ssmult}: {\tt C = A*B} \item {\tt cholmod\_submatrix}: {\tt C = A (i,j)}, where {\tt i} and {\tt j} are arbitrary integer vectors. \item {\tt cholmod\_horzcat}: {\tt C = [A,B]} \item {\tt cholmod\_vertcat}: {\tt C = [A ; B]}. \item {\tt cholmod\_symmetry}: determine symmetry of a matrix. \end{itemize} %------------------------------------------------------------------------------- \subsection{{\tt Supernodal} Module: supernodal sparse Cholesky factorization} %------------------------------------------------------------------------------- The {\tt Supernodal} Module performs supernodal analysis, factorization, and solve. The simplest way to use these routines is via the {\tt Cholesky} Module. This Module does not provide any fill-reducing orderings. It normally operates on matrices ordered by the {\tt Cholesky} Module. It does not require the {\tt Cholesky} Module itself, however. Requires the {\tt Utility} Module, and two external packages: LAPACK and the BLAS. Optionally used by the {\tt Cholesky} Module. All are secondary routines since these functions are more easily used via the {\tt Cholesky} Module. \vspace{0.1in} \noindent Secondary routines: \begin{itemize} \item {\tt cholmod\_super\_symbolic}: supernodal symbolic analysis % \item {\tt cholmod\_super\_symbolic2}: for sparse QR \item {\tt cholmod\_super\_numeric}: supernodal numeric factorization \item {\tt cholmod\_super\_lsolve}: supernodal $\m{Lx}=\m{b}$ solve \item {\tt cholmod\_super\_ltsolve}: supernodal $\m{L}\tr\m{x}=\m{b}$ solve \end{itemize} %------------------------------------------------------------------------------- \subsection{{\tt Partition} Module: graph-partitioning-based orderings} %------------------------------------------------------------------------------- The {\tt Partition} Module provides graph partitioning and graph-partition-based orderings. It includes an interface to CAMD, CCOLAMD, and CSYMAMD, constrained minimum degree ordering methods which order a matrix following constraints determined via nested dissection. Requires the {\tt Utility} and {\tt Cholesky} Modules, and two packages: {\tt METIS 5.1.0}, CAMD, and CCOLAMD. Optionally used by the {\tt Cholesky} Module. All are secondary routines since these are more easily used by the {\tt Cholesky} Module. \vspace{0.1in} \noindent Secondary routines: \begin{itemize} \item {\tt cholmod\_ccolamd}: interface to CCOLAMD ordering \item {\tt cholmod\_csymamd}: interface to CSYMAMD ordering \item {\tt cholmod\_camd}: interface to CAMD ordering % \item {\tt cholmod\_nested\_dissection}: CHOLMOD nested dissection ordering \item {\tt cholmod\_metis}: METIS nested dissection ordering ({\tt METIS\_NodeND}) \item {\tt cholmod\_bisect}: graph partitioner (currently based on METIS) \item {\tt cholmod\_metis\_bisector}: direct interface to {\tt METIS\_NodeComputeSeparator}. \item {\tt cholmod\_collapse\_septree}: pruned a separator tree from {\tt cholmod\_nested\_dissection}. \end{itemize} %------------------------------------------------------------------------------- \newpage \section{CHOLMOD naming convention, parameters, and return values} %------------------------------------------------------------------------------- All routine names, data types, and CHOLMOD library files use the {\tt cholmod\_} prefix. All macros and other {\tt \#define} statements visible to the user program use the {\tt CHOLMOD} prefix. The {\tt cholmod.h} file must be included in user programs that use CHOLMOD: {\footnotesize \begin{verbatim} #include "cholmod.h" \end{verbatim} } \noindent All CHOLMOD routines (in all modules) use the following protocol for return values: \begin{itemize} \item {\tt int}: {\tt TRUE} (1) if successful, or {\tt FALSE} (0) otherwise. (exception: {\tt cholmod\_divcomplex}). \item {\tt int32\_t} or {\tt int64\_t}: a value $\ge 0$ if successful, or -1 otherwise. \item {\tt float} or {\tt double}: a value $\ge 0$ if successful, or -1 otherwise. \item {\tt size\_t}: a value $>$ 0 if successful, or 0 otherwise. \item {\tt void *}: a non-{\tt NULL} pointer to newly allocated memory if successful, or {\tt NULL} otherwise. \item {\tt cholmod\_sparse *}: a non-{\tt NULL} pointer to a newly allocated sparse matrix if successful, or {\tt NULL} otherwise. \item {\tt cholmod\_factor *}: a non-{\tt NULL} pointer to a newly allocated factor if successful, or {\tt NULL} otherwise. \item {\tt cholmod\_triplet *}: a non-{\tt NULL} pointer to a newly allocated triplet matrix if successful, or {\tt NULL} otherwise. \item {\tt cholmod\_dense *}: a non-{\tt NULL} pointer to a newly allocated dense matrix if successful, or {\tt NULL} otherwise. \end{itemize} {\tt TRUE} and {\tt FALSE} are not defined in {\tt cholmod.h}, since they may conflict with the user program. A routine that described here returning {\tt TRUE} or {\tt FALSE} returns 1 or 0, respectively. Any {\tt TRUE}/{\tt FALSE} parameter is true if nonzero, false if zero. \noindent Input, output, and input/output parameters: \begin{itemize} \item Input parameters appear first in the parameter lists of all CHOLMOD routines. They are not modified by CHOLMOD. \item Input/output parameters (except for {\tt Common}) appear next. They must be defined on input, and are modified on output. \item Output parameters are listed next. If they are pointers, they must point to allocated space on input, but their contents are not defined on input. \item Workspace parameters appear next. They are used in only two routines in the Supernodal module. \item The {\tt cholmod\_common *Common} parameter always appears as the last parameter (with two exceptions: {\tt cholmod\_hypot} and {\tt cholmod\_divcomplex}). It is always an input/output parameter. \end{itemize} A floating-point scalar is passed to CHOLMOD as a pointer to a {\tt double} array of size two. The first entry in this array is the real part of the scalar, and the second entry is the imaginary part. The imaginary part is only accessed if the other inputs are complex or zomplex. In some cases the imaginary part is always ignored ({\tt cholmod\_factor\_p}, for example). This method for passing scalars is used when the computations are done both in {\tt double} and single ({\tt float}) precision. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: {\tt cholmod\_common} object} \label{cholmod_common} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_common}: parameters, statistics, and workspace} %--------------------------------------- \input{_common.tex} The {\tt cholmod\_common Common} object contains parameters, statistics, and workspace used within CHOLMOD. The first call to CHOLMOD must be {\tt cholmod\_start}, which initializes this object. %--------------------------------------- \subsection{{\tt cholmod\_start}: start CHOLMOD} %--------------------------------------- \input{_start.tex} Sets the default parameters, clears the statistics, and initializes all workspace pointers to {\tt NULL}. The {\tt int32}/{\tt int64\_t} type is set in {\tt Common->itype}. %--------------------------------------- \subsection{{\tt cholmod\_finish}: finish CHOLMOD} %--------------------------------------- \input{_finish.tex} This must be the last call to CHOLMOD. %--------------------------------------- \subsection{{\tt cholmod\_defaults}: set default parameters} %--------------------------------------- \input{_defaults.tex} Sets the default parameters. %--------------------------------------- \subsection{{\tt cholmod\_maxrank}: maximum update/downdate rank} %--------------------------------------- \input{_maxrank.tex} Returns the maximum rank for an update/downdate. %--------------------------------------- \subsection{{\tt cholmod\_allocate\_work}: allocate workspace} %--------------------------------------- \input{_allocate_work.tex} Allocates workspace in {\tt Common}. The workspace consists of the integer {\tt Head}, {\tt Flag}, and {\tt Iwork} arrays, of size {\tt nrow+1}, {\tt nrow}, and {\tt iworksize}, respectively, and a {\tt double} array {\tt Xwork} of size {\tt xworksize} entries. The {\tt Head} array is normally equal to -1 when it is cleared. If the {\tt Flag} array is cleared, all entries are less than {\tt Common->mark}. The {\tt Iwork} array is not kept in any particular state. The integer type is {\tt int32\_t} or {\tt int64\_t}, depending on whether the {\tt cholmod\_} or {\tt cholmod\_l\_} routines are used. %--------------------------------------- \subsection{{\tt cholmod\_alloc\_work}: allocate workspace} %--------------------------------------- \input{_alloc_work.tex} This is the same as {\tt cholmod\_allocate\_work}, except that the {\tt Xwork} array can be {\tt float} or {\tt double}, as determined by the {\tt dtype} input parameter. %--------------------------------------- \subsection{{\tt cholmod\_free\_work}: free workspace} %--------------------------------------- \input{_free_work.tex} Frees the workspace in {\tt Common}. %--------------------------------------- \subsection{{\tt cholmod\_clear\_flag}: clear Flag array} %--------------------------------------- \input{_clear_flag.tex} Increments {\tt Common->mark} so that the {\tt Flag} array is now cleared. %--------------------------------------- \subsection{{\tt cholmod\_error}: report error} %--------------------------------------- \input{_error.tex} This routine is called when CHOLMOD encounters an error. It prints a message (if printing is enabled), sets {\tt Common->status}. It then calls the user error handler routine {\tt Common->error\_handler}, if it is not {\tt NULL}. %--------------------------------------- \subsection{{\tt cholmod\_dbound}: bound diagonal of $\m{L}$} %--------------------------------------- \input{_dbound.tex} Ensures that entries on the diagonal of $\m{L}$ for an $\m{LL}\tr$ factorization are greater than or equal to {\tt Common->dbound}, when computing in double precision ({\tt double}). For an $\m{LDL}\tr$ factorization, it ensures that the magnitude of the entries of $\m{D}$ are greater than or equal to {\tt Common->dbound}. %--------------------------------------- \subsection{{\tt cholmod\_sbound}: bound diagonal of $\m{L}$} %--------------------------------------- \input{_sbound.tex} Ensures that entries on the diagonal of $\m{L}$ for an $\m{LL}\tr$ factorization are greater than or equal to {\tt Common->sbound}, when computing in single precision ({\tt float}). For an $\m{LDL}\tr$ factorization, it ensures that the magnitude of the entries of $\m{D}$ are greater than or equal to {\tt Common->sbound}. %--------------------------------------- \subsection{{\tt cholmod\_hypot}: {\tt sqrt(x*x+y*y)}} %--------------------------------------- \input{_hypot.tex} Computes the magnitude of a complex number. This routine calls {\tt SuiteSparse\_config\_hypot}. Refer to the {\tt SuiteSparse\_config} package for details. %--------------------------------------- \subsection{{\tt cholmod\_divcomplex}: complex divide} %--------------------------------------- \input{_divcomplex.tex} Divides two complex numbers. This routine calls {\tt SuiteSparse\_config\_divcomplex}. Refer to the {\tt SuiteSparse\_config} package for details. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: {\tt cholmod\_sparse} object} \label{cholmod_sparse} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_sparse}: compressed-column sparse matrix} %--------------------------------------- \input{_sparse.tex} Stores a sparse matrix in compressed-column form. %--------------------------------------- \subsection{{\tt cholmod\_allocate\_sparse}: allocate sparse matrix} %--------------------------------------- \input{_allocate_sparse.tex} Allocates a sparse matrix. Indices and values ({\tt A->i}, {\tt A->x}, and {\tt A->z}) are allocated but not initialized. The matrix returned is valid, has no entries, but contains space enough for {\tt nzmax} entries. %--------------------------------------- \subsection{{\tt cholmod\_free\_sparse}: free sparse matrix} %--------------------------------------- \input{_free_sparse.tex} Frees a sparse matrix. %--------------------------------------- \subsection{{\tt cholmod\_reallocate\_sparse}: reallocate sparse matrix} %--------------------------------------- \input{_reallocate_sparse.tex} Reallocates a sparse matrix, so that it can contain {\tt nznew} entries. %--------------------------------------- \subsection{{\tt cholmod\_nnz}: number of entries in sparse matrix} %--------------------------------------- \input{_nnz.tex} Returns the number of entries in a sparse matrix. %--------------------------------------- \subsection{{\tt cholmod\_speye}: sparse identity matrix} %--------------------------------------- \input{_speye.tex} Returns the sparse identity matrix. %--------------------------------------- \subsection{{\tt cholmod\_spzeros}: sparse zero matrix} %--------------------------------------- \input{_spzeros.tex} Returns the sparse zero matrix. This is another name for {\tt cholmod\_allocate\_sparse}, but with fewer parameters (the matrix is packed, sorted, and unsymmetric). %--------------------------------------- \subsection{{\tt cholmod\_transpose}: transpose sparse matrix} %--------------------------------------- \input{_transpose.tex} Returns the transpose or complex conjugate transpose of a sparse matrix. Three kinds of transposes are available, depending on the {\tt mode} parameter: \begin{itemize} \item 0: do not compute the numerical values; create a {\tt CHOLMOD\_PATTERN} matrix \item 1: array transpose \item 2: complex conjugate transpose (same as 2 if input is real or pattern) \end{itemize} %--------------------------------------- \subsection{{\tt cholmod\_transpose\_unsym}: transpose/permute unsymmetric sparse matrix} %--------------------------------------- \input{_transpose_unsym.tex} Transposes and optionally permutes an unsymmetric sparse matrix. The output matrix must be preallocated before calling this routine. The \verb'mode' parameter is the same as for \verb'cholmod_transpose'. Computes {\tt F=A'}, {\tt F=A(:,f)'} or {\tt F=A(p,f)'}, except that the indexing by {\tt f} does not work the same as the MATLAB notation (see below). {\tt A->stype} must be zero on input, which denotes that the matrix is unsymmetric, with both the upper and lower triangular parts of A are present. {\tt A} may be rectangular. The integer vector {\tt p} is a permutation of {\tt 0:m-1}, and {\tt f} is a subset of {\tt 0:n-1}, where A is {\tt m}-by-{\tt n}. There can be no duplicate entries in {\tt p} or {\tt f}. \noindent The set {\tt f} is held in fset and fsize: \begin{itemize} \item {\tt fset = NULL} means ``{\tt :}'' in MATLAB. {\tt fset} is ignored. \item {\tt fset != NULL} means {\tt f = fset [0..fsize-1]}. \item {\tt fset != NULL} and {\tt fsize = 0} means {\tt f} is the empty set. \end{itemize} Columns not in the set {\tt f} are considered to be zero. That is, if {\tt A} is 5-by-10 then {\tt F=A(:,[3 4])'} is not 2-by-5, but 10-by-5, and rows 3 and 4 of {\tt F} are equal to columns 3 and 4 of {\tt A} (the other rows of {\tt F} are zero). More precisely, in MATLAB notation: \begin{verbatim} [m n] = size (A) F = A notf = ones (1,n) notf (f) = 0 F (:, find (notf)) = 0 F = F' \end{verbatim} If you want the MATLAB equivalent {\tt F=A(p,f)} operation, use {\tt cholmod\_submatrix} instead (which does not compute the transpose). {\tt F->nzmax} must be large enough to hold the matrix {\tt F}. If {\tt F->nz} is present then {\tt F->nz [j]} is equal to the number of entries in column {\tt j} of {\tt F}. {\tt A} can be sorted or unsorted, with packed or unpacked columns. If {\tt f} is present and not sorted in ascending order, then {\tt F} is unsorted (that is, it may contain columns whose row indices do not appear in ascending order). Otherwise, {\tt F} is sorted (the row indices in each column of {\tt F} appear in strictly ascending order). {\tt F} is returned in packed or unpacked form, depending on {\tt F->packed} on input. If {\tt F->packed} is {\tt FALSE}, then {\tt F} is returned in unpacked form ({\tt F->nz} must be present). Each row {\tt i} of {\tt F} is large enough to hold all the entries in row {\tt i} of {\tt A}, even if {\tt f} is provided. That is, {\tt F->i} and {\tt F->x [F->p [i] .. F->p [i] + F->nz [i] - 1]} contain all entries in {\tt A(i,f)}, but {\tt F->p [i+1] - F->p [i]} is equal to the number of nonzeros in {\tt A (i,:)}, not just {\tt A (i,f)}. The {\tt cholmod\_transpose\_unsym} routine is the only operation in CHOLMOD that can produce an unpacked sparse matrix. %--------------------------------------- \subsection{{\tt cholmod\_transpose\_sym}: transpose/permute symmetric sparse matrix} %--------------------------------------- \input{_transpose_sym.tex} Computes {\tt F = A'} or {\tt F = A(p,p)'}, the transpose or permuted transpose, where {\tt A->stype} is nonzero. {\tt A} must be square and symmetric. If {\tt A->stype} $> 0$, then {\tt A} is a symmetric matrix where just the upper part of the matrix is stored. Entries in the lower triangular part may be present, but are ignored. If {\tt A->stype} $< 0$, then {\tt A} is a symmetric matrix where just the lower part of the matrix is stored. Entries in the upper triangular part may be present, but are ignored. If {\tt F=A'}, then {\tt F} is returned sorted; otherwise {\tt F} is unsorted for the {\tt F=A(p,p)'} case. There can be no duplicate entries in {\tt p}. The \verb'mode' parameter is the same as for \verb'cholmod_transpose'. For {\tt cholmod\_transpose\_unsym} and {\tt cholmod\_transpose\_sym}, the output matrix {\tt F} must already be pre-allocated by the caller, with the correct dimensions. If {\tt F} is not valid or has the wrong dimensions, it is not modified. Otherwise, if {\tt F} is too small, the transpose is not computed; the contents of {\tt F->p} contain the column pointers of the resulting matrix, where {\tt F->p [F->ncol] > F->nzmax}. In this case, the remaining contents of {\tt F} are not modified. {\tt F} can still be properly freed with {\tt cholmod\_free\_sparse}. %--------------------------------------- \subsection{{\tt cholmod\_ptranspose}: transpose/permute sparse matrix} %--------------------------------------- \input{_ptranspose.tex} Returns {\tt A'} or {\tt A(p,p)'} if {\tt A} is symmetric. Returns {\tt A'}, {\tt A(:,f)'}, or {\tt A(p,f)'} if {\tt A} is unsymmetric. The \verb'mode' parameter is the same as for \verb'cholmod_transpose'. See {\tt cholmod\_transpose\_unsym} for a discussion of how {\tt f} is used; this usage deviates from the MATLAB notation. Can also return the array transpose. %--------------------------------------- \subsection{{\tt cholmod\_sort}: sort columns of a sparse matrix} %--------------------------------------- \input{_sort.tex} Sorts the columns of the matrix {\tt A}. Returns {\tt A} in packed form, even if it starts as unpacked. Removes entries in the ignored part of a symmetric matrix. %--------------------------------------- \subsection{{\tt cholmod\_band\_nnz}: count entries in a band of a sparse matrix} %--------------------------------------- \input{_band_nnz.tex} This method has the same inputs as \verb'cholmod_band', except that it returns the count of entries instead of returning the new matrix. The \verb'mode' parameter has no effect on this count. %--------------------------------------- \subsection{{\tt cholmod\_band}: extract band of a sparse matrix} %--------------------------------------- \input{_band.tex} Returns {\tt C = tril (triu (A,k1), k2)}. {\tt C} is a matrix consisting of the diagonals of A from {\tt k1} to {\tt k2}. {\tt k=0} is the main diagonal of {\tt A}, {\tt k=1} is the superdiagonal, {\tt k=-1} is the subdiagonal, and so on. If {\tt A} is {\tt m}-by-{\tt n}, then: \begin{itemize} \item {\tt k1=-m} means {\tt C = tril (A,k2)} \item {\tt k2=n} means {\tt C = triu (A,k1)} \item {\tt k1=0} and {\tt k2=0} means {\tt C = diag(A)}, except {\tt C} is a matrix, not a vector \end{itemize} Values of {\tt k1} and {\tt k2} less than {\tt -m} are treated as {\tt -m}, and values greater than {\tt n} are treated as {\tt n}. {\tt A} can be of any symmetry (upper, lower, or unsymmetric); {\tt C} is returned in the same form, and packed. If {\tt A->stype} $> 0$, entries in the lower triangular part of {\tt A} are ignored, and the opposite is true if {\tt A->stype} $< 0$. If {\tt A} has sorted columns, then so does {\tt C}. {\tt C} has the same size as {\tt A}. The \verb'mode' parameter determines how the numerical values are handled. {\tt C} can be returned as a numerical valued matrix (if {\tt A} has numerical values and {\tt mode} $> 0$), as a pattern-only ({\tt mode} $=0$), or as a pattern-only but with the diagonal entries removed ({\tt mode} $< 0$). The xtype of {\tt A} can be pattern or real. Complex or zomplex cases are supported only if {\tt mode} is $\le 0$ (in which case the numerical values are ignored). %--------------------------------------- \subsection{{\tt cholmod\_band\_inplace}: extract band, in place} %--------------------------------------- \input{_band_inplace.tex} Same as {\tt cholmod\_band}, except that it always operates in place. Only packed matrices can be converted in place. %--------------------------------------- \subsection{{\tt cholmod\_aat}: compute $\m{AA}\tr$} %--------------------------------------- \input{_aat.tex} Computes {\tt C = A*A'} or {\tt C = A(:,f)*A(:,f)'}. {\tt A} can be packed or unpacked, sorted or unsorted, but must be stored with both upper and lower parts ({\tt A->stype} of zero). {\tt C} is returned as packed, {\tt C->stype} of zero (both upper and lower parts present), and unsorted. See {\tt cholmod\_ssmult} in the {\tt MatrixOps} Module for a more general matrix-matrix multiply. The xtype of {\tt A} can be pattern or real. Complex or zomplex cases are supported only if {\tt mode} is $\le 0$ (in which case the numerical values are ignored). You can trivially convert {\tt C} to a symmetric upper/lower matrix by changing {\tt C->stype} to 1 or -1, respectively, after calling this routine. %--------------------------------------- \subsection{{\tt cholmod\_copy\_sparse}: copy sparse matrix} %--------------------------------------- \input{_copy_sparse.tex} Returns an exact copy of the input sparse matrix {\tt A}. %--------------------------------------- \subsection{{\tt cholmod\_copy}: copy (and change) sparse matrix} %--------------------------------------- \input{_copy.tex} {\tt C = A}, which allocates {\tt C} and copies {\tt A} into {\tt C}, with possible change of {\tt stype}. The diagonal can optionally be removed. The numerical entries can optionally be copied. This routine differs from {\tt cholmod\_copy\_sparse}, which makes an exact copy of a sparse matrix. {\tt A} can be of any type (packed/unpacked, upper/lower/unsymmetric). {\tt C} is packed and can be of any stype (upper/lower/unsymmetric), except that if {\tt A} is rectangular {\tt C} can only be unsymmetric. If the stype of A and C differ, then the appropriate conversion is made. \noindent There are three cases for {\tt A->stype}: \begin{itemize} \item $<0$, lower: assume {\tt A} is symmetric with just {\tt tril(A)} stored; the rest of {\tt A} is ignored \item $ 0$, unsymmetric: assume {\tt A} is unsymmetric; consider all entries in A \item $>0$, upper: assume {\tt A} is symmetric with just {\tt triu(A)} stored; the rest of {\tt A} is ignored \end{itemize} \noindent There are three cases for the requested symmetry of {\tt C} ({\tt stype} parameter): \begin{itemize} \item $<0$, lower: return just {\tt tril(C)} \item $0$, unsymmetric: return all of {\tt C} \item $>0$, upper: return just {\tt triu(C)} \end{itemize} \noindent This gives a total of nine combinations: \newline {\small \begin{tabular}{ll} \hline Equivalent MATLAB statements & Using {\tt cholmod\_copy} \\ \hline {\tt C = A ; }& {\tt A} unsymmetric, {\tt C} unsymmetric \\ {\tt C = tril (A) ; }& {\tt A} unsymmetric, {\tt C} lower \\ {\tt C = triu (A) ; }& {\tt A} unsymmetric, {\tt C} upper \\ {\tt U = triu (A) ; L = tril (U',-1) ; C = L+U ;} & {\tt A} upper, {\tt C} unsymmetric \\ {\tt C = triu (A)' ; }& {\tt A} upper, {\tt C} lower \\ {\tt C = triu (A) ; }& {\tt A} upper, {\tt C} upper \\ {\tt L = tril (A) ; U = triu (L',1) ; C = L+U ;} & {\tt A} lower, {\tt C} unsymmetric \\ {\tt C = tril (A) ; }& {\tt A} lower, {\tt C} lower \\ {\tt C = tril (A)' ; }& {\tt A} lower, {\tt C} upper \\ \hline \end{tabular}} \vspace{0.1in} The \verb'mode' parameter determines whether a pattern-only copy is made, or whether a numerical copy is make, and also how the transpose is done above for the complex case (conjugate matrix transpose, or non-conjugate array transpose). %--------------------------------------- \subsection{{\tt cholmod\_add}: add sparse matrices} %--------------------------------------- \input{_add.tex} Returns {\tt C = alpha*A + beta*B}. If the {\tt stype} of {\tt A} and {\tt B} match, then {\tt C} has the same {\tt stype}. Otherwise, {\tt C->stype} is zero ({\tt C} is unsymmetric). If the \verb'stype' of any input matrix is nonzero, it must be converted to unsymmetric, controlled by the \verb'mode' parameter. %--------------------------------------- \subsection{{\tt cholmod\_sparse\_xtype}: change sparse xtype} %--------------------------------------- \input{_sparse_xtype.tex} Changes the {\tt xtype} and/or \verb'dtype' of a sparse matrix. The \verb'xtype' can be changed to pattern, real, complex, or zomplex. The \verb'dtype' can be changed to single or double. Changing from complex or zomplex to real discards the imaginary part. The name of this method derives from an earlier version of CHOLMOD where all matrices had an implied \verb'dtype' of \verb'CHOLMOD_DOUBLE'. The method now supports changes to the \verb'dtype'. For backward compatilibilty, the name of this method has not changed, and the \verb'to_xdtype' parameter values of the prior versions are upwards compatible with this version of CHOLMOD. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: {\tt cholmod\_factor} object} \label{cholmod_factor} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_factor} object: a sparse Cholesky factorization} %--------------------------------------- \input{_factor.tex} An $\m{LL}\tr$ or $\m{LDL}\tr$ factorization in simplicial or supernodal form. A simplicial factor is very similar to a {\tt cholmod\_sparse} matrix. For an $\m{LDL}\tr$ factorization, the diagonal matrix $\m{D}$ is stored as the diagonal of $\m{L}$; the unit-diagonal of $\m{L}$ is not stored. %--------------------------------------- \subsection{{\tt cholmod\_free\_factor}: free factor} %--------------------------------------- \input{_free_factor.tex} Frees a factor. %--------------------------------------- \subsection{{\tt cholmod\_allocate\_factor}: allocate factor} %--------------------------------------- \input{_allocate_factor.tex} Allocates a factor and sets it to identity. %--------------------------------------- \subsection{{\tt cholmod\_alloc\_factor}: allocate factor} %--------------------------------------- \input{_alloc_factor.tex} Allocates a factor and sets it to identity ({\tt double} or {\tt float}). %--------------------------------------- \subsection{{\tt cholmod\_reallocate\_factor}: reallocate factor} %--------------------------------------- \input{_reallocate_factor.tex} Reallocates a simplicial factor so that it can contain {\tt nznew} entries. %--------------------------------------- \subsection{{\tt cholmod\_change\_factor}: change factor} %--------------------------------------- \input{_change_factor.tex} Change the numeric or symbolic, $\m{LL}\tr$ or $\m{LDL}\tr$, simplicial or super, packed or unpacked, and monotonic or non-monotonic status of a {\tt cholmod\_factor} object. There are four basic classes of factor types: \begin{enumerate} \item simplicial symbolic: Consists of two size-{\tt n} arrays: the fill-reducing permutation ({\tt L->Perm}) and the nonzero count for each column of L ({\tt L->ColCount}). All other factor types also include this information. {\tt L->ColCount} may be exact (obtained from the analysis routines), or it may be a guess. During factorization, and certainly after update/downdate, the columns of {\tt L} can have a different number of nonzeros. {\tt L->ColCount} is used to allocate space. {\tt L->ColCount} is exact for the supernodal factorizations. The nonzero pattern of {\tt L} is not kept. \item simplicial numeric: These represent {\tt L} in a compressed column form. The variants of this type are: \begin{itemize} \item $\m{LDL}\tr$: {\tt L} is unit diagonal. Row indices in column {\tt j} are located in {\tt L->i [L->p [j] ... L->p [j] + L->nz [j]]}, and corresponding numeric values are in the same locations in {\tt L->x}. The total number of entries is the sum of {\tt L->nz [j]}. The unit diagonal is not stored; {\tt D} is stored on the diagonal of {\tt L} instead. {\tt L->p} may or may not be monotonic. The order of storage of the columns in {\tt L->i} and {\tt L->x} is given by a doubly-linked list ({\tt L->prev} and {\tt L->next}). {\tt L->p} is of size {\tt n+1}, but only the first {\tt n} entries are used. For the complex case, {\tt L->x} is stored interleaved with real and imaginary parts, and is of size {\tt 2*lnz*sizeof(double)} or {\tt 2*lnz*sizeof(float)}. For the zomplex case, {\tt L->x} is of size {\tt lnz*sizeof(double)} or {\tt lnz*sizeof(float)} and holds the real part; {\tt L->z} is the same size and holds the imaginary part. \item $\m{LL}\tr$: This is identical to the $\m{LDL}\tr$ form, except that the non-unit diagonal of {\tt L} is stored as the first entry in each column of {\tt L}. \end{itemize} \item supernodal symbolic: A representation of the nonzero pattern of the supernodes for a supernodal factorization. There are {\tt L->nsuper} supernodes. Columns {\tt L->super [k]} to {\tt L->super [k+1]-1} are in the {\tt k}th supernode. The row indices for the {\tt k}th supernode are in {\tt L->s [L->pi [k] ... L->pi [k+1]-1]}. The numerical values are not allocated ({\tt L->x}), but when they are they will be located in {\tt L->x [L->px [k] ... L->px [k+1]-1]}, and the {\tt L->px} array is defined in this factor type. For the complex case, {\tt L->x} is stored interleaved with real/imaginary parts, and is of size \newline {\tt 2*L->xsize*sizeof(double)} or {\tt 2*L->xsize*sizeof(float)}. The zomplex supernodal case is not supported, since it is not compatible with LAPACK and the BLAS. \item supernodal numeric: Always an $\m{LL}\tr$ factorization. {\tt L} has a non-unit diagonal. {\tt L->x} contains the numerical values of the supernodes, as described above for the supernodal symbolic factor. For the complex case, {\tt L->x} is stored interleaved, and is of size {\tt 2*L->xsize*sizeof(double)} or {\tt 2*L->xsize*sizeof(double)}. The zomplex supernodal case is not supported, since it is not compatible with LAPACK and the BLAS. \end{enumerate} In all cases, the row indices in each column ({\tt L->i} for simplicial {\tt L} and {\tt L->s} for supernodal {\tt L}) are kept sorted from low indices to high indices. This means the diagonal of {\tt L} (or {\tt D} for a $\m{LDL}\tr$ factorization) is always kept as the first entry in each column. The elimination tree is not kept. The parent of node {\tt j} can be found as the second row index in the {\tt j}th column. If column {\tt j} has no off-diagonal entries then node {\tt j} is a root of the elimination tree. The {\tt cholmod\_change\_factor} routine can do almost all possible conversions. It cannot do the following conversions: \begin{itemize} \item Simplicial numeric types cannot be converted to a supernodal symbolic type. This would simultaneously deallocate the simplicial pattern and numeric values and reallocate uninitialized space for the supernodal pattern. This isn't useful for the user, and not needed by CHOLMOD's own routines either. \item Only a symbolic factor (simplicial to supernodal) can be converted to a supernodal numeric factor. \end{itemize} Some conversions are meant only to be used internally by other CHOLMOD routines, and should not be performed by the end user. They allocate space whose contents are undefined: \begin{itemize} \item converting from simplicial symbolic to supernodal symbolic. \item converting any factor to supernodal numeric. \end{itemize} Supports all xtypes, except that there is no supernodal zomplex L. The \verb'to_xtype' parameter is used only when converting from symbolic to numeric or numeric to symbolic. It cannot be used to convert a numeric xtype (real, complex, or zomplex) to a different numeric {\tt xtype}. It also cannot change the \verb'dtype' of a factor (from double to single, for example). For those conversions, use \verb'cholmod_factor_xtype' instead. %--------------------------------------- \subsection{{\tt cholmod\_pack\_factor}: pack the columns of a factor} %--------------------------------------- \input{_pack_factor.tex} Pack the columns of a simplicial $\m{LDL}\tr$ or $\m{LL}\tr$ factorization. This can be followed by a call to {\tt cholmod\_reallocate\_factor} to reduce the size of {\tt L} to the exact size required by the factor, if desired. Alternatively, you can leave the size of {\tt L->i} and {\tt L->x} the same, to allow space for future updates/rowadds. Each column is reduced in size so that it has at most {\tt Common->grow2} free space at the end of the column. Does nothing and returns silently if given any other type of factor. Does not force the columns of {\tt L} to be monotonic. It thus differs from \begin{verbatim} cholmod_change_factor (xtype, L->is_ll, FALSE, TRUE, TRUE, L, Common) \end{verbatim} which packs the columns and ensures that they appear in monotonic order. %--------------------------------------- \subsection{{\tt cholmod\_reallocate\_column}: reallocate one column of a factor} %--------------------------------------- \input{_reallocate_column.tex} Reallocates the space allotted to a single column of $\m{L}$. %--------------------------------------- \subsection{{\tt cholmod\_factor\_to\_sparse}: sparse matrix copy of a factor} %--------------------------------------- \input{_factor_to_sparse.tex} Returns a column-oriented sparse matrix containing the pattern and values of a simplicial or supernodal numerical factor, and then converts the factor into a simplicial symbolic factor. If {\tt L} is already packed, monotonic, and simplicial (which is the case when {\tt cholmod\_factorize} uses the simplicial Cholesky factorization algorithm) then this routine requires only a small amount of time and memory, independent of {\tt n}. It only operates on numeric factors (real, complex, or zomplex). It does not change {\tt L->xtype} (the resulting sparse matrix has the same {\tt xtype} as {\tt L}). If this routine fails, {\tt L} is left unmodified. %--------------------------------------- \subsection{{\tt cholmod\_copy\_factor}: copy factor} %--------------------------------------- \input{_copy_factor.tex} Returns an exact copy of a factor. %--------------------------------------- \subsection{{\tt cholmod\_factor\_xtype}: change factor xtype} %--------------------------------------- \input{_factor_xtype.tex} Changes the {\tt xtype} and/or \verb'dtype' of a sparse factorization. The \verb'xtype' can be changed to real, complex, or zomplex (not to pattern). The \verb'dtype' can be changed to single or double. Changing from complex or zomplex to real discards the imaginary part. A supernodal factor cannot be changed to the zomplex \verb'xtype'. A factor cannot be converted to an \verb'xtype' of pattern-only with this method; use \verb'cholmod_change_factor' for that operation. The name of this method derives from an earlier version of CHOLMOD where all matrices had an implied \verb'dtype' of \verb'CHOLMOD_DOUBLE'. The method now supports changes to the \verb'dtype'. For backward compatilibilty, the name of this method has not changed, and the \verb'to_xdtype' parameter values of the prior versions are upwards compatible with this version of CHOLMOD. %--------------------------------------- \subsection{How many entries are in a CHOLMOD sparse Cholesky factorization?} %--------------------------------------- This is a simple question perhaps a surprisingly complex question to answer. For a sparse Cholesky factorization in CHOLMOD, there are at least 6 ways to answer this question. First of all, the kind of factorization ($LL'$ or $LDL'$) doesn't affect this answer, if the $n$ entries in unit diagonal of $L$ in the $LDL'$ factorization are excluded. So all of the discussion here includes this simplification, and ``\verb'L''' can be considered the same as ``\verb'LD'.'' In strictly increasing order of size (except that definition 5 can be larger or smaller than 3 and/or 4): \begin{enumerate} \item The number of entries not numerically equal to zero. This is a bit ephemeral since it's affected by roundoff, denormals flushing to zero, and so on. Computing this requires converting a factor to sparse matrix with \verb'cholmod_factor_to_sparse', followed by \verb'cholmod_drop' with a \verb'tol' of zero, and then a call to \verb'cholmod_nnz'. There is no method in CHOLMOD to compute this otherwise. This number is \verb'nnz(L)' in MATLAB after the built-in \verb'R=chol(A)' (which uses CHOLMOD and where \verb"R=L'") or in my MATLAB interface as \verb'R=chol2(A)' or \verb'L=lchol(A)', since a valid MATLAB sparse matrix cannot include any explicit entries that are numerically equal to zero. However, such a matrix cannot be used in an update/downdate, nor in my internal solve routines, since those methods require the chordal property of \verb'L'. That property is broken if entries are dropped because of exact numerical cancellation. Zero entries are not dropped by \verb'LD=ldlchol(A)', which works fine in practice but the matrix \verb'LD' is thus technically not a valid MATLAB sparse matrix. \item The number of entries in the filled graph of \verb'L'. This is a very stable number, and doesn't depend on roundoff, data structures, or factorization method used. It only depends on the symbolic pattern of \verb'A', and the fill-reducing ordering. Some entries can be exactly zero because of roundoff but this is ignored. This is returned as \verb'Common->lnz' after the call to \verb'cholmod_analyze'. The value is not saved in \verb'L' itself because it can change with update/downdates. This can be computed in MATLAB via any of the following, where any fill-reducing ordering would first need to be applied to the input matrix \verb'A': {\small \begin{verbatim} [count] = symbfact (A, ...) ; % built-in sum (count) [count] = symbfact2 (A, ...) ; % mine, but it's the same as symbfact sum (count) [count, h, parent, post, R] = symbfact (A, ...) ; % built-in nnz (R) [count, h, parent, post, R] = symbfact2 (A, ...) ; % mine, the same nnz (R) [count, h, parent, post, L] = symbfact2 (A, ..., 'L') ; % mine, with L not R nnz (L) \end{verbatim}} Internally the built-in MATLAB \verb'symbfact' function calls CHOLMOD. The \verb'L' or \verb'R' matrix returned above has the entire pattern, but where each entry is equal to one. \item The number of entries in the supernodal \verb'L', which is like (2) but with added entries because of relaxed amalgamation. This affected by everything in (2), but also the relaxed amalgamation parameters. Entries in the upper trianglar part of each supernode are excluded, since mathematically, each supernode is lower trapezoidal (with a square lower triangular part stacked on top of a rectangular part). This number is computed internally during the computation to change a factor from a \verb'cholmod_factor' to a \verb'cholmod_sparse' object, in \verb'cholmod_factor_to_sparse' and \verb'cholmod_change_factor', when \verb'L' is converted to a simplicial form that is packed and monotonic. \item The same as (3), but with entries in the upper triangular part included. This is the bare minimum space required to hold \verb'L' in supernodal form. The value \verb'L->xsize' is a tight bound on this number (almost always identical to this value, but I can't guarantee this will always be true). \item The number of entries in \verb'L' after any update/downdates. The factorization would no longer be supernodal, since doing any update/downdate converts a superondal \verb'L' into a simplicial one (supernodes are exploited to reduce the time for each update/downdate, however, but this is done dynamically). A downdate can delete entries but I don't keep track of when this happens. I would need to keep \verb'L' as a collection of multisets, and update/downdate the multiplicity of each entry. I actually did this for a while but it's costly. So instead I have a \verb'cholmod_resymbol' method to prune these down to (2). This number can be computed by \verb'sum(L->nz[0..n-1])', if \verb'L' is simplicial. \item The size of the data structure to hold the entries of \verb'L'. This number if \verb'L->xsize' for the supernodal case, and \verb'L->nzmax' otherwise. For a supernodal \verb'L', \verb'L->xsize' treats each supernode as rectangular, not lower trapezoidal. For a simplicial \verb'L,' after update/downdate, I can include gaps in the columns of \verb'L' to allow for room for growth. This value can be obtained from any factor object, either supernodal or simplicial, and either symbolic or numeric, with the following expression: \begin{verbatim} (L->is_super) ? L->xsize : L->nzmax \end{verbatim} If \verb'L' is simplicial, this number can change when \verb'L' converted from symbolic to numeric, depending on the \verb'to_packed' parameter. However, at any stage this value does give the size of the \verb'L->x' array (and the \verb'L->z' array if zomplex) that holds the numerical values. If \verb'L' is symbolic (supernodal or simplicial) these arrays are not yet allocated, and both \verb'L->x' and \verb'L->z' are \verb'NULL'. This number is in terms of entires, not bytes, so to get the number of bytes, multiply by \verb'sizeof(float)' if \verb'L->dtype' is \verb'CHOLMOD_SINGLE', by \verb'sizeof(double)' if \verb'L->dtype' is \verb'CHOLMOD_DOUBLE', and again by another factor of 2 if the matrix to factorize is complex or zomplex. \end{enumerate} Except for the simple expressions for: \begin{itemize} \item (2) \verb'Common->lnz' \item and (5) \verb'(L->is_super) ? L->xsize : L->nzmax', \end{itemize} there is no user-callable method in CHOLMOD to compute these values. I may consider adding such a method in a future release. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: {\tt cholmod\_dense} object} \label{cholmod_dense} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_dense} object: a dense matrix} %--------------------------------------- \input{_dense.tex} Contains a dense matrix. %--------------------------------------- \subsection{{\tt cholmod\_allocate\_dense}: allocate dense matrix} %--------------------------------------- \input{_allocate_dense.tex} Allocates a dense matrix. %--------------------------------------- \subsection{{\tt cholmod\_free\_dense}: free dense matrix} %--------------------------------------- \input{_free_dense.tex} Frees a dense matrix. %--------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_zeros}: dense zero matrix} %--------------------------------------- \input{_zeros.tex} Returns an all-zero dense matrix. %--------------------------------------- \subsection{{\tt cholmod\_ones}: dense matrix, all ones} %--------------------------------------- \input{_ones.tex} Returns a dense matrix with each entry equal to one. %--------------------------------------- \subsection{{\tt cholmod\_eye}: dense identity matrix} %--------------------------------------- \input{_eye.tex} Returns a dense identity matrix. %--------------------------------------- \subsection{{\tt cholmod\_ensure\_dense}: ensure dense matrix has a given size and type} %--------------------------------------- \input{_ensure_dense.tex} Ensures a dense matrix has a given size and type. %--------------------------------------- \subsection{{\tt cholmod\_sparse\_to\_dense}: dense matrix copy of a sparse matrix} %--------------------------------------- \input{_sparse_to_dense.tex} Returns a dense copy of a sparse matrix. %--------------------------------------- \subsection{{\tt cholmod\_dense\_nnz}: number of nonzeros in a dense matrix} %--------------------------------------- \input{_dense_nnz.tex} Returns a count of the number of nonzero entries in a dense matrix. %--------------------------------------- \subsection{{\tt cholmod\_dense\_to\_sparse}: sparse matrix copy of a dense matrix} %--------------------------------------- \input{_dense_to_sparse.tex} Returns a sparse copy of a dense matrix. %--------------------------------------- \subsection{{\tt cholmod\_copy\_dense}: copy dense matrix} %--------------------------------------- \input{_copy_dense.tex} Returns a copy of a dense matrix. %--------------------------------------- \subsection{{\tt cholmod\_copy\_dense2}: copy dense matrix (preallocated)} %--------------------------------------- \input{_copy_dense2.tex} Returns a copy of a dense matrix, placing the result in a preallocated matrix {\tt Y}. %--------------------------------------- \subsection{{\tt cholmod\_dense\_xtype}: change dense matrix xtype} %--------------------------------------- \input{_dense_xtype.tex} Changes the {\tt xtype} and/or \verb'dtype' of a dense matrix. The \verb'xtype' can change to real, complex, or zomplex (not pattern-only). The \verb'dtype' can change to single or double. Changing from complex or zomplex to real discards the imaginary part. A dense matrix cannot be converted to an \verb'xtype' of pattern-only. The name of this method derives from an earlier version of CHOLMOD where all matrices had an implied \verb'dtype' of \verb'CHOLMOD_DOUBLE'. The method now supports changes to the \verb'dtype'. For backward compatilibilty, the name of this method has not changed, and the \verb'to_xdtype' parameter values of the prior versions are upwards compatible with this version of CHOLMOD. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: {\tt cholmod\_triplet} object} \label{cholmod_triplet} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_triplet} object: sparse matrix in triplet form} %--------------------------------------- \input{_triplet.tex} Contains a sparse matrix in triplet form. %--------------------------------------- \subsection{{\tt cholmod\_allocate\_triplet}: allocate triplet matrix} %--------------------------------------- \input{_allocate_triplet.tex} Allocates a triplet matrix. %--------------------------------------- \subsection{{\tt cholmod\_free\_triplet}: free triplet matrix} %--------------------------------------- \input{_free_triplet.tex} Frees a triplet matrix. %--------------------------------------- \subsection{{\tt cholmod\_triplet\_to\_sparse}: sparse matrix copy of a triplet matrix} %--------------------------------------- \input{_triplet_to_sparse.tex} Returns a sparse matrix copy of a triplet matrix. If the triplet matrix is symmetric with just the lower part present ({\tt T->stype} $< 0$), then entries in the upper part are transposed and placed in the lower part when converting to a sparse matrix. Similarly, if the triplet matrix is symmetric with just the upper part present ({\tt T->stype} $> 0$), then entries in the lower part are transposed and placed in the upper part when converting to a sparse matrix. Any duplicate entries are summed. %--------------------------------------- \subsection{{\tt cholmod\_reallocate\_triplet}: reallocate triplet matrix} %--------------------------------------- \input{_reallocate_triplet.tex} Reallocates a triplet matrix so that it can hold {\tt nznew} entries. %--------------------------------------- \subsection{{\tt cholmod\_sparse\_to\_triplet}: triplet matrix copy of a sparse matrix} %--------------------------------------- \input{_sparse_to_triplet.tex} Returns a triplet matrix copy of a sparse matrix. %--------------------------------------- \subsection{{\tt cholmod\_copy\_triplet}: copy triplet matrix} %--------------------------------------- \input{_copy_triplet.tex} Returns an exact copy of a triplet matrix. %--------------------------------------- \subsection{{\tt cholmod\_triplet\_xtype}: change triplet xtype} %--------------------------------------- \input{_triplet_xtype.tex} Changes the {\tt xtype} and/or \verb'dtype' of a triplet matrix. The \verb'xtype' can change to pattern, real, complex, or zomplex, and the \verb'dtype' can change to single or double. Changing from complex or zomplex to real discards the imaginary part. The name of this method derives from an earlier version of CHOLMOD where all matrices had an implied \verb'dtype' of \verb'CHOLMOD_DOUBLE'. The method now supports changes to the \verb'dtype'. For backward compatilibilty, the name of this method has not changed, and the \verb'to_xdtype' parameter values of the prior versions are upwards compatible with this version of CHOLMOD. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: memory management} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_malloc}: allocate memory} %--------------------------------------- \input{_malloc.tex} Allocates a block of memory of size {\tt n*size}, using the {\tt SuiteSparse\_config.malloc\_func} function pointer (default is to use the ANSI C {\tt malloc} routine). A value of {\tt n=0} is treated as {\tt n=1}. If not successful, {\tt NULL} is returned and {\tt Common->status} is set to {\tt CHOLMOD\_OUT\_OF\_MEMORY}. %--------------------------------------- \subsection{{\tt cholmod\_calloc}: allocate and clear memory} %--------------------------------------- \input{_calloc.tex} Allocates a block of memory of size {\tt n*size}, using the {\tt SuiteSparse\_config.calloc\_func} function pointer (default is to use the ANSI C {\tt calloc} routine). A value of {\tt n=0} is treated as {\tt n=1}. If not successful, {\tt NULL} is returned and {\tt Common->status} is set to {\tt CHOLMOD\_OUT\_OF\_MEMORY}. %--------------------------------------- \subsection{{\tt cholmod\_free}: free memory} %--------------------------------------- \input{_free.tex} Frees a block of memory of size {\tt n*size}, using the {\tt SuiteSparse\_config.free\_func} function pointer (default is to use the ANSI C {\tt free} routine). The size of the block ({\tt n} and {\tt size}) is only required so that CHOLMOD can keep track of its current and peak memory usage. This is a useful statistic, and it can also help in tracking down memory leaks. After the call to {\tt cholmod\_finish}, the count of allocated blocks ({\tt Common->malloc\_count}) should be zero, and the count of bytes in use ({\tt Common->memory\_inuse}) also should be zero. If you allocate a block with one size and free it with another, the {\tt Common->memory\_inuse} count will be wrong, but CHOLMOD will not have a memory leak. %--------------------------------------- \subsection{{\tt cholmod\_realloc}: reallocate memory} %--------------------------------------- \input{_realloc.tex} Reallocates a block of memory whose current size {\tt n*size}, and whose new size will be {\tt nnew*size} if successful, using the {\tt SuiteSparse\_config.calloc\_func} function pointer (default is to use the ANSI C {\tt realloc} routine). If the reallocation is not successful, {\tt p} is returned unchanged and {\tt Common->status} is set to {\tt CHOLMOD\_OUT\_OF\_MEMORY}. The value of {\tt n} is set to {\tt nnew} if successful, or left unchanged otherwise. A value of {\tt nnew=0} is treated as {\tt nnew=1}. %--------------------------------------- \subsection{{\tt cholmod\_realloc\_multiple}: reallocate memory} %--------------------------------------- \input{_realloc_multiple.tex} Reallocates multiple blocks of memory, all with the same number of items (but with different item sizes). Either all reallocations succeed, or all are returned to their original size. %------------------------------------------------------------------------------- \newpage \section{{\tt Utility} Module: version control} %------------------------------------------------------------------------------- \subsection{{\tt cholmod\_version}: return current CHOLMOD version} \input{_version.tex} Returns the CHOLMOD version number, so that it can be tested at run time, even if the caller does not have access to the CHOLMOD include files. For example, for a CHOLMOD version 3.2.1, the {\tt version} array will contain 3, 2, and 1, in that order. This function appears in CHOLMOD 2.1.1 and later. You can check if the function exists with the {\tt CHOLMOD\_HAS\_VERSION\_FUNCTION} macro, so that the following code fragment works in any version of CHOLMOD: \begin{verbatim} #ifdef CHOLMOD_HAS_VERSION_FUNCTION v = cholmod_version (NULL) ; #else v = CHOLMOD_VERSION ; #endif \end{verbatim} Note that {\tt cholmod\_version} and {\tt cholmod\_l\_version} have identical prototypes. Both use {\tt int}'s. Unlike all other CHOLMOD functions, this function does not take the {\tt Common} object as an input parameter. %------------------------------------------------------------------------------- \newpage \section{{\tt Check} Module routines} %------------------------------------------------------------------------------- No CHOLMOD routines print anything, except for the {\tt cholmod\_print\_*} routines in the {\tt Check} Module, and the {\tt cholmod\_error} routine. The {\tt SuiteSparse\_config.printf\_function} is a pointer to {\tt printf} by default; you can redirect the output of CHOLMOD by redefining this pointer. If the function pointer is {\tt NULL}, CHOLMOD does not print anything. The {\tt Common->print} parameter determines how much detail is printed. Each value of {\tt Common->print} listed below also prints the items listed for smaller values of {\tt Common->print}: \begin{itemize} \item 0: print nothing; check the data structures and return {\tt TRUE} or {\tt FALSE}. \item 1: print error messages. \item 2: print warning messages. \item 3: print a one-line summary of the object. \item 4: print a short summary of the object (first and last few entries). \item 5: print the entire contents of the object. \end{itemize} Values less than zero are treated as zero, and values greater than five are treated as five. %--------------------------------------- \subsection{{\tt cholmod\_check\_common}: check Common object} %--------------------------------------- \input{_check_common.tex} Check if the {\tt Common} object is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_common}: print Common object} %--------------------------------------- \input{_print_common.tex} Print the {\tt Common} object and check if it is valid. This prints the CHOLMOD parameters and statistics. %--------------------------------------- \subsection{{\tt cholmod\_check\_sparse}: check sparse matrix} %--------------------------------------- \input{_check_sparse.tex} Check if a sparse matrix is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_sparse}: print sparse matrix} %--------------------------------------- \input{_print_sparse.tex} Print a sparse matrix and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_check\_dense}: check dense matrix} %--------------------------------------- \input{_check_dense.tex} Check if a dense matrix is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_dense}: print dense matrix} %--------------------------------------- \input{_print_dense.tex} Print a dense matrix and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_check\_factor}: check factor} %--------------------------------------- \input{_check_factor.tex} Check if a factor is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_factor}: print factor} %--------------------------------------- \input{_print_factor.tex} Print a factor and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_check\_triplet}: check triplet matrix} %--------------------------------------- \input{_check_triplet.tex} Check if a triplet matrix is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_triplet}: print triplet matrix} %--------------------------------------- \input{_print_triplet.tex} Print a triplet matrix and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_check\_subset}: check subset} %--------------------------------------- \input{_check_subset.tex} Check if a subset is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_subset}: print subset} %--------------------------------------- \input{_print_subset.tex} Print a subset and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_check\_perm}: check permutation} %--------------------------------------- \input{_check_perm.tex} Check if a permutation is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_perm}: print permutation} %--------------------------------------- \input{_print_perm.tex} Print a permutation and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_check\_parent}: check elimination tree} %--------------------------------------- \input{_check_parent.tex} Check if an elimination tree is valid. %--------------------------------------- \subsection{{\tt cholmod\_print\_parent}: print elimination tree} %--------------------------------------- \input{_print_parent.tex} Print an elimination tree and check if it is valid. %--------------------------------------- \subsection{{\tt cholmod\_read\_triplet}: read triplet matrix from file} %--------------------------------------- \input{_read_triplet.tex} Read a sparse matrix in triplet form, using the the {\tt coord} Matrix Market format (http://www.nist.gov/MatrixMarket). Skew-symmetric and complex symmetric matrices are returned with both upper and lower triangular parts present (an stype of zero). Real symmetric and complex Hermitian matrices are returned with just their upper or lower triangular part, depending on their stype. The Matrix Market {\tt array} data type for dense matrices is not supported (use {\tt cholmod\_read\_dense} for that case). If the first line of the file starts with {\tt \%\%MatrixMarket}, then it is interpreted as a file in Matrix Market format. The header line is optional. If present, this line must have the following format: \vspace{0.1in} {\tt \%\%MatrixMarket matrix coord} {\em type storage} \vspace{0.1in} \noindent where {\em type} is one of: {\tt real}, {\tt complex}, {\tt pattern}, or {\tt integer}, and {\em storage} is one of: {\tt general}, {\tt hermitian}, {\tt symmetric}, or {\tt skew-symmetric}. In CHOLMOD, these roughly correspond to the {\tt xtype} (pattern, real, complex, or zomplex) and {\tt stype} (unsymmetric, symmetric/upper, and symmetric/lower). The strings are case-insensitive. Only the first character (or the first two for skew-symmetric) is significant. The {\tt coord} token can be replaced with {\tt array} in the Matrix Market format, but this format not supported by {\tt cholmod\_read\_triplet}. The {\tt integer} type is converted to real. The {\em type} is ignored; the actual type (real, complex, or pattern) is inferred from the number of tokens in each line of the file (2: pattern, 3: real, 4: complex). This is compatible with the Matrix Market format. The matrix is read in {\tt double} precision. To read a matrix in either double or single precision ({\tt double} or {\tt float}), use \verb'cholmod_read_triplet2'. A storage of {\tt general} implies an stype of zero (see below). A storage of {\tt symmetric} and {\tt hermitian} imply an stype of -1. Skew-symmetric and complex symmetric matrices are returned with an stype of 0. Blank lines, any other lines starting with ``{\tt \%}'' are treated as comments, and are ignored. The first non-comment line contains 3 or 4 integers: \vspace{0.1in} {\em nrow ncol nnz stype} \vspace{0.1in} \noindent where {\em stype} is optional (stype does not appear in the Matrix Market format). The matrix is {\em nrow}-by-{\em ncol}. The following {\em nnz} lines (excluding comments) each contain a single entry. Duplicates are permitted, and are summed in the output matrix. If stype is present, it denotes the storage format for the matrix. \begin{itemize} \item stype = 0 denotes an unsymmetric matrix (same as Matrix Market {\tt general}). \item stype = -1 denotes a symmetric or Hermitian matrix whose lower triangular entries are stored. Entries may be present in the upper triangular part, but these are ignored (same as Matrix Market {\tt symmetric} for the real case, {\tt hermitian} for the complex case). \item stype = 1 denotes a symmetric or Hermitian matrix whose upper triangular entries are stored. Entries may be present in the lower triangular part, but these are ignored. This format is not available in the Matrix Market format. \end{itemize} If neither the stype nor the Matrix Market header are present, then the stype is inferred from the rest of the data. If the matrix is rectangular, or has entries in both the upper and lower triangular parts, then it is assumed to be unsymmetric (stype=0). If only entries in the lower triangular part are present, the matrix is assumed to have stype = -1. If only entries in the upper triangular part are present, the matrix is assumed to have stype = 1. Each nonzero consists of one line with 2, 3, or 4 entries. All lines must have the same number of entries. The first two entries are the row and column indices of the nonzero. If 3 entries are present, the 3rd entry is the numerical value, and the matrix is real. If 4 entries are present, the 3rd and 4th entries in the line are the real and imaginary parts of a complex value. The matrix can be either 0-based or 1-based. It is first assumed to be one-based (compatible with Matrix Market), with row indices in the range 1 to ncol and column indices in the range 1 to nrow. If a row or column index of zero is found, the matrix is assumed to be zero-based (with row indices in the range 0 to ncol-1 and column indices in the range 0 to nrow-1). This test correctly determines that all Matrix Market matrices are in 1-based form. For symmetric pattern-only matrices, the kth diagonal (if present) is set to one plus the degree of the row k or column k (whichever is larger), and the off-diagonals are set to -1. A symmetric pattern-only matrix with a zero-free diagonal is thus converted into a symmetric positive definite matrix. All entries are set to one for an unsymmetric pattern-only matrix. This differs from the MatrixMarket format ({\tt A = mmread ('file')} returns a binary pattern for A for symmetric pattern-only matrices). To return a binary format for all pattern-only matrices, use {\tt A = mread('file',1)}. Example matrices that follow this format can be found in the {\tt CHOLMOD/Demo/Matrix} and \newline {\tt CHOLMOD/Tcov/Matrix} directories. You can also try any of the matrices in the Matrix Market collection at http://www.nist.gov/MatrixMarket. %--------------------------------------- \subsection{{\tt cholmod\_read\_triplet2}: read triplet matrix from file} %--------------------------------------- \input{_read_triplet2.tex} Identical to \verb'cholmod_read_triplet', except that the dtype can be specified (\verb'CHOLMOD_DOUBLE' or \verb'CHOLMOD_SINGLE'). %--------------------------------------- \subsection{{\tt cholmod\_read\_sparse}: read sparse matrix from file} %--------------------------------------- \input{_read_sparse.tex} Read a sparse matrix in triplet form from a file (using {\tt cholmod\_read\_triplet}) and convert to a CHOLMOD sparse matrix. The Matrix Market format is used. If {\tt Common->prefer\_upper} is {\tt TRUE} (the default case), a symmetric matrix is returned stored in upper-triangular form ({\tt A->stype} is 1). Otherwise, it is left in its original form, either upper or lower. % The matrix is read in {\tt double} precision. To read a matrix in either double or single precision ({\tt double} or {\tt float}), use \verb'cholmod_read_sparse2'. %--------------------------------------- \subsection{{\tt cholmod\_read\_sparse2}: read sparse matrix from file} %--------------------------------------- \input{_read_sparse2.tex} Identical to \verb'cholmod_read_sparse', except that the dtype can be specified (\verb'CHOLMOD_DOUBLE' or \verb'CHOLMOD_SINGLE'). %--------------------------------------- \subsection{{\tt cholmod\_read\_dense}: read dense matrix from file} %--------------------------------------- \input{_read_dense.tex} Read a dense matrix from a file, using the {\tt array} Matrix Market format \newline (http://www.nist.gov/MatrixMarket). % The matrix is read in {\tt double} precision. To read a matrix in either double or single precision ({\tt double} or {\tt float}), use \verb'cholmod_read_dense2'. %--------------------------------------- \subsection{{\tt cholmod\_read\_dense2}: read dense matrix from file} %--------------------------------------- \input{_read_dense2.tex} Identical to \verb'cholmod_read_dense', except that the dtype can be specified (\verb'CHOLMOD_DOUBLE' or \verb'CHOLMOD_SINGLE'). %--------------------------------------- \subsection{{\tt cholmod\_read\_matrix}: read a matrix from file} %--------------------------------------- \input{_read_matrix.tex} Read a sparse or dense matrix from a file, in Matrix Market format. Returns a {\tt void} pointer to either a {\tt cholmod\_triplet}, {\tt cholmod\_sparse}, or {\tt cholmod\_dense} object. % The matrix is read in {\tt double} precision. To read a matrix in either double or single precision ({\tt double} or {\tt float}), use \verb'cholmod_read_matrix2'. %--------------------------------------- \subsection{{\tt cholmod\_read\_matrix2}: read a matrix from file} %--------------------------------------- \input{_read_matrix2.tex} Identical to \verb'cholmod_read_matrix', except that the dtype can be specified (\verb'CHOLMOD_DOUBLE' or \verb'CHOLMOD_SINGLE'). %--------------------------------------- \subsection{{\tt cholmod\_write\_sparse}: write a sparse matrix to a file} %--------------------------------------- \input{_write_sparse.tex} Write a sparse matrix to a file in Matrix Market format. Optionally include comments, and print explicit zero entries given by the pattern of the {\tt Z} matrix. If not NULL, the {\tt Z} matrix must have the same dimensions and stype as {\tt A}. Returns the symmetry in which the matrix was printed (1 to 7) or -1 on failure. See the {\tt cholmod\_symmetry} function for a description of the return codes. If {\tt A} and {\tt Z} are sorted on input, and either unsymmetric (stype = 0) or symmetric-lower (stype $< 0$), and if {\tt A} and {\tt Z} do not overlap, then the triplets are sorted, first by column and then by row index within each column, with no duplicate entries. If all the above holds except stype $> 0$, then the triplets are sorted by row first and then column. %--------------------------------------- \subsection{{\tt cholmod\_write\_dense}: write a dense matrix to a file} %--------------------------------------- \input{_write_dense.tex} Write a dense matrix to a file in Matrix Market format. Optionally include comments. Returns $> 0$ if successful, -1 otherwise (1 if rectangular, 2 if square). A dense matrix is written in "general" format; symmetric formats in the Matrix Market standard are not exploited. %------------------------------------------------------------------------------- \newpage \section{{\tt Cholesky} Module routines} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_analyze}: symbolic factorization} %--------------------------------------- \input{_analyze.tex} Orders and analyzes a matrix (either simplicial or supernodal), in preparation for numerical factorization via {\tt cholmod\_factorize} or via the ``expert'' routines {\tt cholmod\_rowfac} and {\tt cholmod\_super\_numeric}. In the symmetric case, {\tt A} or {\tt A(p,p)} is analyzed, where {\tt p} is the fill-reducing ordering. In the unsymmetric case, {\tt A*A'} or {\tt A(p,:)*A(p,:)'} is analyzed. The {\tt cholmod\_analyze\_p} routine can be given a user-provided permutation {\tt p} (see below). The default ordering strategy is to first try AMD. The ordering quality is analyzed, and if AMD obtains an ordering where {\tt nnz(L)} is greater than or equal to {\tt 5*nnz(tril(A))} (or {\tt 5*nnz(tril(A*A'))} if {\tt A} is unsymmetric) and the floating-point operation count for the subsequent factorization is greater than or equal to {\tt 500*nnz(L)}, then METIS is tried (if installed). For {\tt cholmod\_analyze\_p}, the user-provided ordering is also tried. This default behavior is obtained when {\tt Common->nmethods} is zero. In this case, methods 0, 1, and 2 in {\tt Common->method[...]} are reset to user-provided, AMD, and METIS, respectively. The ordering with the smallest {\tt nnz(L)} is kept. If {\tt Common->default\_nesdis} is true (nonzero), then CHOLMOD's nested dissection (NESDIS) is used for the default strategy described above, in place of METIS. Other ordering options can be requested. These include: \begin{enumerate} \item natural: A is not permuted to reduce fill-in. \item user-provided: a permutation can be provided to {\tt cholmod\_analyze\_p}. \item AMD: approximate minimum degree (AMD for the symmetric case, COLAMD for the {\tt A*A'} case). \item METIS: nested dissection with {\tt METIS\_NodeND} \item {\tt NESDIS}: CHOLMOD's nested dissection using {\tt METIS\_NodeComputeSeparator}, followed by a constrained minimum degree (CAMD or CSYMAMD for the symmetric case, CCOLAMD for the {\tt A*A'} case). This is typically slower than METIS, but typically provides better orderings. \end{enumerate} Multiple ordering options can be tried (up to 9 of them), and the best one is selected (the one that gives the smallest number of nonzeros in the simplicial factor L). If one method fails, {\tt cholmod\_analyze} keeps going, and picks the best among the methods that succeeded. This routine fails (and returns {\tt NULL}) if either the initial memory allocation fails, all ordering methods fail, or the supernodal analysis (if requested) fails. Change {\tt Common->nmethods} to the number of methods you wish to try. By default, the 9 methods available are: \begin{enumerate} \item user-provided permutation (only for {\tt cholmod\_analyze\_p}). \item AMD with default parameters. \item METIS with default parameters. \item {\tt NESDIS} with default parameters: stopping the partitioning when the graph is of size {\tt nd\_small} = 200 or less, remove nodes with more than {\tt max (16, prune\_dense * sqrt (n))} nodes where {\tt prune\_dense} = 10, and follow partitioning with constrained minimum degree ordering (CAMD for the symmetric case, CCOLAMD for the unsymmetric case). \item natural ordering (with weighted postorder). \item NESDIS, {\tt nd\_small} = 20000, {\tt prune\_dense} = 10. \item NESDIS, {\tt nd\_small} = 4, {\tt prune\_dense} = 10, no constrained minimum degree. \item NESDIS, {\tt nd\_small} = 200, {\tt prune\_dense} = 0. \item COLAMD for {\tt A*A'} or AMD for {\tt A} \end{enumerate} You can modify these 9 methods and the number of methods tried by changing parameters in the {\tt Common} argument. If you know the best ordering for your matrix, set {\tt Common->nmethods} to 1 and set {\tt Common->method[0].ordering} to the requested ordering method. Parameters for each method can also be modified (refer to the description of {\tt cholmod\_common} for details). Note that it is possible for METIS to terminate your program if it runs out of memory. This is not the case for any CHOLMOD or minimum degree ordering routine (AMD, COLAMD, CAMD, CCOLAMD, or CSYMAMD). Since {\tt NESDIS} relies on METIS, it too can terminate your program. The selected ordering is followed by a weighted postorder of the elimination tree by default (see {\tt cholmod\_postorder} for details), unless {\tt Common->postorder} is set to {\tt FALSE}. The postorder does not change the number of nonzeros in $\m{L}$ or the floating-point operation count. It does improve performance, particularly for the supernodal factorization. If you truly want the natural ordering with no postordering, you must set {\tt Common->postorder} to {\tt FALSE}. The factor {\tt L} is returned as simplicial symbolic if {\tt Common->supernodal} is {\tt CHOLMOD\_SIMPLICIAL} (zero) or as supernodal symbolic if {\tt Common->supernodal} is {\tt CHOLMOD\_SUPERNODAL} (two). If \newline {\tt Common->supernodal} is {\tt CHOLMOD\_AUTO} (one), then {\tt L} is simplicial if the flop count per nonzero in {\tt L} is less than {\tt Common->supernodal\_switch} (default: 40), and supernodal otherwise. In both cases, {\tt L->xtype} is {\tt CHOLMOD\_PATTERN}. A subsequent call to {\tt cholmod\_factorize} will perform a simplicial or supernodal factorization, depending on the type of {\tt L}. For the simplicial case, {\tt L} contains the fill-reducing permutation ({\tt L->Perm}) and the counts of nonzeros in each column of {\tt L} ({\tt L->ColCount}). For the supernodal case, {\tt L} also contains the nonzero pattern of each supernode. If a simplicial factorization is selected, it will be $\m{LDL}\tr$ by default, since this is the kind required by the {\tt Modify} Module. CHOLMOD does not include a supernodal $\m{LDL}\tr$ factorization, so if a supernodal factorization is selected, it will be in the form $\m{LL}\tr$. The $\m{LDL}\tr$ method can be used to factorize positive definite matrices and indefinite matrices whose leading minors are well-conditioned (2-by-2 pivoting is not supported). The $\m{LL}\tr$ method is restricted to positive definite matrices. To factorize a large indefinite matrix, set {\tt Common->supernodal} to {\tt CHOLMOD\_SIMPLICIAL}, and the simplicial $\m{LDL}\tr$ method will always be used. This will be significantly slower than a supernodal $\m{LL}\tr$ factorization, however. Refer to {\tt cholmod\_transpose\_unsym} for a description of {\tt f}. %--------------------------------------- \subsection{{\tt cholmod\_factorize}: numeric factorization} %--------------------------------------- \input{_factorize.tex} Computes the numerical factorization of a symmetric matrix. The inputs to this routine are a sparse matrix {\tt A} and the symbolic factor {\tt L} from {\tt cholmod\_analyze} or a prior numerical factor {\tt L}. If {\tt A} is symmetric, this routine factorizes {\tt A(p,p)}. where p is the fill-reducing permutation ({\tt L->Perm}). If {\tt A} is unsymmetric, {\tt A(p,:)*A(p,:)'} is factorized. The nonzero pattern of the matrix {\tt A} must be the same as the matrix passed to {\tt cholmod\_analyze} for the supernodal case. For the simplicial case, it can be different, but it should be the same for best performance. A simplicial factorization or supernodal factorization is chosen, based on the type of the factor {\tt L}. If {\tt L->is\_super} is {\tt TRUE}, a supernodal $\m{LL}\tr$ factorization is computed. Otherwise, a simplicial numeric factorization is computed, either $\m{LL}\tr$ or $\m{LDL}\tr$, depending on {\tt Common->final\_ll} (the default for the simplicial case is to compute an $\m{LDL}\tr$ factorization). Once the factorization is complete, it can be left as is or optionally converted into any simplicial numeric type, depending on the {\tt Common->final\_*} parameters. If converted from a supernodal to simplicial type, and {\tt Common->final\_resymbol} is {\tt TRUE}, then numerically zero entries in {\tt L} due to relaxed supernodal amalgamation are removed from the simplicial factor (they are always left in the supernodal form of {\tt L}). Entries that are numerically zero but present in the simplicial symbolic pattern of {\tt L} are left in place (the graph of {\tt L} remains chordal). This is required for the update/downdate/rowadd/rowdel routines to work properly. If the matrix is not positive definite the routine returns {\tt TRUE}, but {\tt Common->status} is set to {\tt CHOLMOD\_NOT\_POSDEF} and {\tt L->minor} is set to the column at which the failure occurred. Columns {\tt L->minor} to {\tt L->n-1} are set to zero. Supports any xtype (pattern, real, complex, or zomplex), except that the input matrix {\tt A} cannot be pattern-only and any dtype (double or single). If {\tt L} is simplicial, its numeric xtype matches {\tt A} on output. If {\tt L} is supernodal, its xtype is real if {\tt A} is real, or complex if {\tt A} is complex or zomplex. CHOLMOD does not provide a supernodal zomplex factor, since it is incompatible with how complex numbers are stored in LAPACK and the BLAS. If the \verb'L' factor on input is a purely symbolic factorizatin (with \verb'L->xtype' of \verb'CHOLMOD_PATTERN', then it is converted to a numeric factorization with same dtype as A. Otherwise, the dtypes of L and A must match. %--------------------------------------- \subsection{{\tt cholmod\_analyze\_p}: symbolic factorization, given permutation} %--------------------------------------- \input{_analyze_p.tex} Identical to {\tt cholmod\_analyze}, except that a user-provided permutation {\tt p} can be provided, and the set {\tt f} for the unsymmetric case can be provided. The matrices {\tt A(:,f)*A(:,f)'} or {\tt A(p,f)*A(p,f)'} can be analyzed in the the unsymmetric case. %--------------------------------------- \subsection{{\tt cholmod\_factorize\_p}: numeric factorization, given permutation} %--------------------------------------- \input{_factorize_p.tex} Identical to {\tt cholmod\_factorize}, but with additional options. The set {\tt f} can be provided for the unsymmetric case; {\tt A(p,f)*A(p,f)'} is factorized. The term {\tt beta*I} can be added to the matrix before it is factorized, where {\tt beta} is real. Only the real part, {\tt beta[0]}, is used. %--------------------------------------- \subsection{{\tt cholmod\_solve}: solve a linear system} %--------------------------------------- \input{_solve.tex} Returns a solution {\tt X} that solves one of the following systems: \begin{tabular}{ll|ll} \hline system & {\tt sys} parameter & system & {\tt sys} parameter \\ $\m{Ax}=\m{b}$ & 0: {\tt CHOLMOD\_A} & & \\ $\m{LDL}\tr\m{x}=\m{b}$ & 1: {\tt CHOLMOD\_LDLt} & $\m{L}\tr\m{x}=\m{b}$ & 5: {\tt CHOLMOD\_Lt} \\ $\m{LDx}=\m{b}$ & 2: {\tt CHOLMOD\_LD} & $\m{Dx}=\m{b}$ & 6: {\tt CHOLMOD\_D} \\ $\m{DL}\tr\m{x}=\m{b}$ & 3: {\tt CHOLMOD\_DLt} & $\m{x}=\m{Pb}$ & 7: {\tt CHOLMOD\_P} \\ $\m{Lx}=\m{b}$ & 4: {\tt CHOLMOD\_L} & $\m{x}=\m{P}\tr\m{b}$ & 8: {\tt CHOLMOD\_Pt} \\ \hline \end{tabular} The factorization can be simplicial $\m{LDL}\tr$, simplicial $\m{LL}\tr$, or supernodal $\m{LL}\tr$. For an $\m{LL}\tr$ factorization, $\m{D}$ is the identity matrix. Thus {\tt CHOLMOD\_LD} and {\tt CHOLMOD\_L} solve the same system if an $\m{LL}\tr$ factorization was performed, for example. This is one of the few routines in CHOLMOD for which the xtype of the input arguments need not match. If both {\tt L} and {\tt B} are real, then {\tt X} is returned real. If either is complex or zomplex, {\tt X} is returned as either complex or zomplex, depending on the {\tt Common->prefer\_zomplex} parameter (default is complex). This routine does not check to see if the diagonal of $\m{L}$ or $\m{D}$ is zero, because sometimes a partial solve can be done with an indefinite or singular matrix. If you wish to check in your own code, test {\tt L->minor}. If {\tt L->minor == L->n}, then the matrix has no zero diagonal entries. If {\tt k = L->minor < L->n}, then {\tt L(k,k)} is zero for an $\m{LL}\tr$ factorization, or {\tt D(k,k)} is zero for an $\m{LDL}\tr$ factorization. Iterative refinement is not performed, but this can be easily done with the {\tt MatrixOps} Module. See {\tt Demo/cholmod\_demo.c} for an example. The dtypes of \verb'L' and \verb'B' must match, and \verb'X' is returned with the same dtype. %--------------------------------------- \subsection{{\tt cholmod\_spsolve}: solve a linear system} %--------------------------------------- \input{_spsolve.tex} Identical to {\tt cholmod\_solve}, except that {\tt B} and {\tt X} are sparse. This function converts {\tt B} to full format, solves the system, and then converts {\tt X} back to sparse. If you want to solve with a sparse {\tt B} and get just a partial solution back in {\tt X} (corresponding to the pattern of {\tt B}), use {\tt cholmod\_solve2} below. %--------------------------------------- \subsection{{\tt cholmod\_solve2}: solve a linear system, reusing workspace} %--------------------------------------- \input{_solve2.tex} Solve a linear system, optionally reusing workspace from a prior call to {\tt cholmod\_solve2}. The inputs to this function are the same as {\tt cholmod\_solve}, with the addition of three parameters: {\tt X}, {\tt Y}, and {\tt E}. The dense matrix {\tt X} is the solution on output. On input, {\tt \&X} can point to a NULL matrix, or be the wrong size. If that is the case, it is freed and allocated to be the proper size. If {\tt X} has the right size and type on input, then the allocation is skipped. In contrast, the {\tt cholmod\_solve} function always allocates its output {\tt X}. This {\tt cholmod\_solve2} function allows you to reuse the memory space of a prior {\tt X}, thereby saving time. The two workspace matrices {\tt Y} and {\tt E} can also be reused between calls. You must free {\tt X} {\tt Y}, and {\tt E} yourself, when your computations are done. Below is an example of usage. Note that {\tt X} {\tt Y}, and {\tt E} must be defined on input (either NULL, or valid dense matrices). \begin{verbatim} cholmod_dense *X = NULL, *Y = NULL, *E = NULL ; ... cholmod_l_solve2 (sys, L, B1, NULL, &X, NULL, &Y, &E, Common) ; cholmod_l_solve2 (sys, L, B2, NULL, &X, NULL, &Y, &E, Common) ; cholmod_l_solve2 (sys, L, B3, NULL, &X, NULL, &Y, &E, Common) ; cholmod_l_free_dense (&X, Common) ; cholmod_l_free_dense (&Y, Common) ; cholmod_l_free_dense (&E, Common) ; \end{verbatim} The equivalent when using {\tt cholmod\_solve} is: \begin{verbatim} cholmod_dense *X = NULL, *Y = NULL, *E = NULL ; ... X = cholmod_l_solve (sys, L, B1, Common) ; cholmod_l_free_dense (&X, Common) ; X = cholmod_l_solve (sys, L, B2, Common) ; cholmod_l_free_dense (&X, Common) ; X = cholmod_l_solve (sys, L, B3, Common) ; cholmod_l_free_dense (&X, Common) ; \end{verbatim} Both methods work fine, but in the second method with {\tt cholmod\_solve}, the internal workspaces ({\tt Y} and {\tt E}) and the solution ({\tt X}) are allocated and freed on each call. The {\tt cholmod\_solve2 function} can also solve for a subset of the solution vector {\tt X}, if the optional {\tt Bset} parameter is non-NULL. The right-hand-side {\tt B} must be a single column vector, and its complexity (real, complex, zomplex) must match that of {\tt L}. The vector {\tt B} is dense, but it is assumed to be zero except for row indices specified in {\tt Bset}. The vector {\tt Bset} must be a sparse column vector, of dimension the same as {\tt B}. Only the pattern of {\tt Bset} is used. The solution {\tt X} (a dense column vector) is modified on output, but is defined only in the rows defined by the sparse vector {\tt Xset}. {\tt Bset} is ignored when solving with {\tt sys} equal to {\tt CHOLMOD\_P} or {\tt CHOLMOD\_Pt}). The entries in {\tt Bset} are a subset of {\tt Xset} (except if {\tt sys} is {\tt CHOLMOD\_P} or {\tt CHOLMOD\_Pt}). No memory allocations are done if the outputs and internal workspaces ({\tt X}, {\tt Xset}, {\tt Y}, and {\tt E}) have been allocated by a prior call (or if allocated by the user). To let {\tt cholmod\_solve2} allocate these outputs and workspaces for you, simply initialize them to NULL (as in the example above). Since it is possible for this function to reallocate these 4 arrays, you should always re-acquire the pointers to their internal data ({\tt X->x} for example) after calling {\tt cholmod\_solve2}, since they may change. They normally will not change except in the first call to this function. On the first call to {\tt cholmod\_solve2} when {\tt Bset} is NULL, the factorization is converted from supernodal to simplicial, if needed. The inverse permutation is also computed and stored in the factorization object, {\tt L}. This can take a modest amount of time. Subsequent calls to {\tt cholmod\_solve2} with a small {\tt Bset} are very fast (both asymptotically and in practice). The dtypes of all parameters must match. You can find an example of how to use {\tt cholmod\_solve2} in the four demo programs, {\tt cholmod\_*\_demo}. %--------------------------------------- \subsection{{\tt cholmod\_etree}: find elimination tree} %--------------------------------------- \input{_etree.tex} Computes the elimination tree of {\tt A} or {\tt A'*A}. In the symmetric case, the upper triangular part of {\tt A} is used. Entries not in this part of the matrix are ignored. Computing the etree of a symmetric matrix from just its lower triangular entries is not supported. In the unsymmetric case, all of {\tt A} is used, and the etree of {\tt A'*A} is computed. Refer to \cite{Liu90a} for a discussion of the elimination tree and its use in sparse Cholesky factorization. %--------------------------------------- \subsection{{\tt cholmod\_rowcolcounts}: nonzeros counts of a factor} %--------------------------------------- \input{_rowcolcounts.tex} Computes the row and column counts of the Cholesky factor {\tt L} of the matrix {\tt A} or {\tt A*A'}. The etree and its postordering must already be computed (see {\tt cholmod\_etree} and {\tt cholmod\_postorder}) and given as inputs to this routine. For the symmetric case ($\m{LL}\tr=\m{A}$), {\tt A} must be stored in symmetric/lower form ({\tt A->stype = -1}). In the unsymmetric case, {\tt A*A'} or {\tt A(:,f)*A(:,f)'} can be analyzed. The fundamental floating-point operation count is returned in {\tt Common->fl} (this excludes extra flops due to relaxed supernodal amalgamation). Refer to {\tt cholmod\_transpose\_unsym} for a description of {\tt f}. The algorithm is described in \cite{GilbertLiNgPeyton01,GilbertNgPeyton94}. % J. Gilbert, E. Ng, B. Peyton, "An efficient algorithm to compute row and % column counts for sparse Cholesky factorization", SIAM J. Matrix Analysis \& % Applic., vol 15, 1994, pp. 1075-1091. % % J. Gilbert, X. Li, E. Ng, B. Peyton, "Computing row and column counts for % sparse QR and LU factorization", BIT, vol 41, 2001, pp. 693-710. %--------------------------------------- \subsection{{\tt cholmod\_analyze\_ordering}: analyze a permutation} %--------------------------------------- \input{_analyze_ordering.tex} Given a matrix {\tt A} and its fill-reducing permutation, compute the elimination tree, its (non-weighted) postordering, and the number of nonzeros in each column of {\tt L}. Also computes the flop count, the total nonzeros in {\tt L}, and the nonzeros in {\tt tril(A)} ({\tt Common->fl}, {\tt Common->lnz}, and {\tt Common->anz}). In the unsymmetric case, {\tt A(p,f)*A(p,f)'} is analyzed, and {\tt Common->anz} is the number of nonzero entries in the lower triangular part of the product, not in {\tt A} itself. Refer to {\tt cholmod\_transpose\_unsym} for a description of {\tt f}. The column counts of {\tt L}, flop count, and other statistics from {\tt cholmod\_rowcolcounts} are not computed if {\tt ColCount} is {\tt NULL}. %--------------------------------------- \subsection{{\tt cholmod\_amd}: interface to AMD} %--------------------------------------- \input{_amd.tex} CHOLMOD interface to the AMD ordering package. Orders {\tt A} if the matrix is symmetric. On output, {\tt Perm [k] = i} if row/column {\tt i} of {\tt A} is the {\tt k}th row/column of {\tt P*A*P'}. This corresponds to {\tt A(p,p)} in MATLAB notation. If A is unsymmetric, {\tt cholmod\_amd} orders {\tt A*A'} or {\tt A(:,f)*A(:,f)'}. On output, {\tt Perm [k] = i} if row/column {\tt i} of {\tt A*A'} is the {\tt k}th row/column of {\tt P*A*A'*P'}. This corresponds to {\tt A(p,:)*A(p,:)'} in MATLAB notation. If {\tt f} is present, {\tt A(p,f)*A(p,f)'} is the permuted matrix. Refer to {\tt cholmod\_transpose\_unsym} for a description of {\tt f}. Computes the flop count for a subsequent $\m{LL}\tr$ factorization, the number of nonzeros in {\tt L}, and the number of nonzeros in the matrix ordered ({\tt A}, {\tt A*A'} or {\tt A(:,f)*A(:,f)'}). These statistics are returned in {\tt Common->fl}, {\tt Common->lnz}, and {\tt Common->anz}, respectively. %--------------------------------------- \subsection{{\tt cholmod\_colamd}: interface to COLAMD} %--------------------------------------- \input{_colamd.tex} CHOLMOD interface to the COLAMD ordering package. Finds a permutation {\tt p} such that the Cholesky factorization of {\tt P*A*A'*P'} is sparser than {\tt A*A'}, using COLAMD. If the {\tt postorder} input parameter is {\tt TRUE}, the column elimination tree is found and postordered, and the COLAMD ordering is then combined with its postordering (COLAMD itself does not perform this postordering). {\tt A} must be unsymmetric ({\tt A->stype = 0}). %--------------------------------------- \subsection{{\tt cholmod\_rowfac}: row-oriented Cholesky factorization} %--------------------------------------- \input{_rowfac.tex} Full or incremental numerical $\m{LDL}\tr$ or $\m{LL}\tr$ factorization (simplicial, not supernodal). {\tt cholmod\_factorize} is the ``easy'' wrapper for this code, but it does not provide access to incremental factorization. The algorithm is the row-oriented, up-looking method described in \cite{Davis05}. See also \cite{Liu86c}. No 2-by-2 pivoting (or any other pivoting) is performed. {\tt cholmod\_rowfac} computes the full or incremental $\m{LDL}\tr$ or $\m{LL}\tr$ factorization of {\tt A+beta*I} (where {\tt A} is symmetric) or {\tt A*F+beta*I} (where {\tt A} and {\tt F} are unsymmetric and only the upper triangular part of {\tt A*F+beta*I} is used). It computes {\tt L} (and {\tt D}, for $\m{LDL}\tr$) one row at a time. The input scalar {\tt beta} is real; only the real part ({\tt beta[0]}) is used. {\tt L} can be a simplicial symbolic or numeric ({\tt L->is\_super} must be {\tt FALSE}). A symbolic factor is converted immediately into a numeric factor containing the identity matrix. For a full factorization, use {\tt kstart = 0} and {\tt kend = nrow}. The existing nonzero entries (numerical values in {\tt L->x} and {\tt L->z} for the zomplex case, and indices in {\tt L->i}) are overwritten. To compute an incremental factorization, select {\tt kstart} and {\tt kend} as the range of rows of {\tt L} you wish to compute. Rows {\tt kstart} to {\tt kend-1} of {\tt L} will be computed. A correct factorization will be computed only if all descendants of all nodes {\tt kstart} to {\tt kend-1} in the elimination tree have been factorized by a prior call to this routine, and if rows {\tt kstart} to {\tt kend-1} have not been factorized. This condition is {\bf not} checked on input. In the symmetric case, {\tt A} must be stored in upper form ({\tt A->stype} is greater than zero). The matrix {\tt F} is not accessed and may be {\tt NULL}. Only columns {\tt kstart} to {\tt kend-1} of {\tt A} are accessed. In the unsymmetric case, the typical case is {\tt F=A'}. Alternatively, if {\tt F=A(:,f)'}, then this routine factorizes the matrix {\tt S = beta*I + A(:,f)*A(:,f)'}. The product {\tt A*F} is assumed to be symmetric; only the upper triangular part of {\tt A*F} is used. {\tt F} must be of size {\tt A->ncol} by {\tt A->nrow}. If the \verb'L' factor on input is a purely symbolic factorization (with \verb'L->xtype' of \verb'CHOLMOD_PATTERN'), then it is converted to a numeric factorization with same dtype as A. Otherwise, the dtypes of L and A must match. % J. Liu, "A compact row storage scheme for Cholesky factors", ACM Trans. % Math. Software, vol 12, 1986, pp. 127-148. %--------------------------------------- \subsection{{\tt cholmod\_row\_subtree}: pattern of row of a factor} %--------------------------------------- \input{_row_subtree.tex} Compute the nonzero pattern of the solution to the lower triangular system \begin{verbatim} L(0:k-1,0:k-1) * x = A (0:k-1,k) \end{verbatim} if {\tt A} is symmetric, or \begin{verbatim} L(0:k-1,0:k-1) * x = A (0:k-1,:) * A (:,k)' \end{verbatim} if {\tt A} is unsymmetric. This gives the nonzero pattern of row {\tt k} of {\tt L} (excluding the diagonal). The pattern is returned postordered, according to the subtree of the elimination tree rooted at node {\tt k}. The symmetric case requires {\tt A} to be in symmetric-upper form. The result is returned in {\tt R}, a pre-allocated sparse matrix of size {\tt nrow}-by-1, with {\tt R->nzmax >= nrow}. {\tt R} is assumed to be packed ({\tt Rnz [0]} is not updated); the number of entries in {\tt R} is given by {\tt Rp [0]}. %--------------------------------------- \subsection{{\tt cholmod\_row\_lsubtree}: pattern of row of a factor} %--------------------------------------- \input{_row_lsubtree.tex} Identical to {\tt cholmod\_row\_subtree}, except the elimination tree is found from {\tt L} itself, not {\tt Parent}. Also, {\tt F=A'} is not provided; the nonzero pattern of the {\tt k}th column of {\tt F} is given by {\tt Fi} and {\tt fnz} instead. %--------------------------------------- \subsection{{\tt cholmod\_resymbol}: re-do symbolic factorization} %--------------------------------------- \input{_resymbol.tex} Recompute the symbolic pattern of {\tt L}. Entries not in the symbolic pattern of the factorization of {\tt A(p,p)} or {\tt F*F'}, where {\tt F=A(p,f)} or {\tt F=A(:,f)}, are dropped, where {\tt p = L->Perm} is used to permute the input matrix {\tt A}. Refer to {\tt cholmod\_transpose\_unsym} for a description of {\tt f}. If an entry in {\tt L} is kept, its numerical value does not change. This routine is used after a supernodal factorization is converted into a simplicial one, to remove zero entries that were added due to relaxed supernode amalgamation. It can also be used after a series of downdates to remove entries that would no longer be present if the matrix were factorized from scratch. A downdate ({\tt cholmod\_updown}) does not remove any entries from {\tt L}. %--------------------------------------- \subsection{{\tt cholmod\_resymbol\_noperm}: re-do symbolic factorization} %--------------------------------------- \input{_resymbol_noperm.tex} Identical to {\tt cholmod\_resymbol}, except that the fill-reducing ordering {\tt L->Perm} is not used. %--------------------------------------- \subsection{{\tt cholmod\_postorder}: tree postorder} %--------------------------------------- \input{_postorder.tex} Postorder a tree. The tree is either an elimination tree (the output from {\tt cholmod\_etree}) or a component tree (from {\tt cholmod\_nested\_dissection}). An elimination tree is a complete tree of {\tt n} nodes with {\tt Parent [j] > j} or {\tt Parent [j] = -1} if j is a root. On output {\tt Post [0..n-1]} is a complete permutation vector; {\tt Post [k] = j} if node {\tt j} is the {\tt k}th node in the postordered elimination tree, where {\tt k} is in the range 0 to {\tt n-1}. A component tree is a subset of {\tt 0:n-1}. {\tt Parent [j] = -2} if node {\tt j} is not in the component tree. {\tt Parent [j] = -1} if {\tt j} is a root of the component tree, and {\tt Parent [j]} is in the range 0 to {\tt n-1} if {\tt j} is in the component tree but not a root. On output, {\tt Post [k]} is defined only for nodes in the component tree. {\tt Post [k] = j} if node {\tt j} is the {\tt k}th node in the postordered component tree, where {\tt k} is in the range 0 to the number of components minus 1. Node {\tt j} is ignored and not included in the postorder if {\tt Parent [j] < -1}. As a result, {\tt cholmod\_check\_parent (Parent, ...)} and {\tt cholmod\_check\_perm (Post, ...)} fail if used for a component tree and its postordering. An optional node weight can be given. When starting a postorder at node {\tt j}, the children of {\tt j} are ordered in decreasing order of their weight. If no weights are given ({\tt Weight} is {\tt NULL}) then children are ordered in decreasing order of their node number. The weight of a node must be in the range 0 to {\tt n-1}. Weights outside that range are silently converted to that range (weights $<$ 0 are treated as zero, and weights $\ge$ {\tt n} are treated as {\tt n-1}). %--------------------------------------- \subsection{{\tt cholmod\_rcond}: reciprocal condition number} %--------------------------------------- \input{_rcond.tex} Returns a rough estimate of the reciprocal of the condition number: the minimum entry on the diagonal of {\tt L} (or absolute entry of {\tt D} for an $\m{LDL}\tr$ factorization) divided by the maximum entry. {\tt L} can be real, complex, or zomplex. Returns -1 on error, 0 if the matrix is singular or has a zero or NaN entry on the diagonal of {\tt L}, 1 if the matrix is 0-by-0, or {\tt min(diag(L))/max(diag(L))} otherwise. Never returns NaN; if {\tt L} has a NaN on the diagonal it returns zero instead. %------------------------------------------------------------------------------- \newpage \section{{\tt Modify} Module routines} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_updown}: update/downdate} %--------------------------------------- \input{_updown.tex} Updates/downdates the $\m{LDL}\tr$ factorization (symbolic, then numeric), by computing a new factorization of \[ \new{\m{L}}\new{\m{D}}\new{\m{L}}\tr = \m{LDL}\tr \pm \m{CC}\tr \] where $\new{\m{L}}$ denotes the new factor. {\tt C} must be sorted. It can be either packed or unpacked. As in all CHOLMOD routines, the columns of {\tt L} are sorted on input, and also on output. If {\tt L} does not contain a simplicial numeric $\m{LDL}\tr$ factorization, it is converted into one. Thus, a supernodal $\m{LL}\tr$ factorization can be passed to {\tt cholmod\_updown}. A symbolic {\tt L} is converted into a numeric identity matrix. If the initial conversion fails, the factor is returned unchanged. If memory runs out during the update, the factor is returned as a simplicial symbolic factor. That is, everything is freed except for the fill-reducing ordering and its corresponding column counts (typically computed by {\tt cholmod\_analyze}). Note that the fill-reducing permutation {\tt L->Perm} is not used. The row indices of {\tt C} refer to the rows of {\tt L}, not {\tt A}. If your original system is $\m{LDL}\tr = \m{PAP}\tr$ (where $\m{P} =$ {\tt L->Perm}), and you want to compute the $\m{LDL}\tr$ factorization of $\m{A}+\m{CC}\tr$, then you must permute $\m{C}$ first. That is, if \[ \m{PAP}\tr = \m{LDL}\tr \] is the initial factorization, then \[ \m{P}(\m{A}+\m{CC}\tr)\m{P}\tr = \m{PAP}\tr+\m{PCC}\tr\m{P}\tr = \m{LDL}\tr + (\m{PC})(\m{PC})\tr = \m{LDL}\tr + \new{\m{C}}\new{\m{C}}\tr \] where $\new{\m{C}} = \m{PC}$. You can use the {\tt cholmod\_submatrix} routine in the {\tt MatrixOps} Module to permute {\tt C}, with: \begin{verbatim} Cnew = cholmod_submatrix (C, L->Perm, L->n, NULL, -1, TRUE, TRUE, Common) ; \end{verbatim} Note that the {\tt sorted} input parameter to {\tt cholmod\_submatrix} must be {\tt TRUE}, because {\tt cholmod\_updown} requires {\tt C} with sorted columns. Only real matrices are supported (double or single). The algorithms are described in \cite{DavisHager99,DavisHager01}. %--------------------------------------- \subsection{{\tt cholmod\_updown\_solve}: update/downdate of a factorization and a solution} %--------------------------------------- \input{_updown_solve.tex} Identical to {\tt cholmod\_updown}, except the system $\m{Lx}=\m{b}$ is also updated/downdated. The new system is $\new{\m{L}}\new{\m{x}}=\m{b} + \Delta \m{b}$. The old solution $\m{x}$ is overwritten with $\new{\m{x}}$. Note that as in the update/downdate of $\m{L}$ itself, the fill-reducing permutation {\tt L->Perm} is not used. The vectors $\m{x}$ and $\m{b}$ are in the permuted ordering. %--------------------------------------- \subsection{{\tt cholmod\_rowadd}: add row to factor} %--------------------------------------- \input{_rowadd.tex} Adds a row and column to an $\m{LDL}\tr$ factorization. The {\tt k}th row and column of {\tt L} must be equal to the {\tt k}th row and column of the identity matrix on input. Only real matrices are supported (double or single). The dtypes of all matrices must match, except when \verb'L' is symbolic (with an xtype of \verb'CHOLMOD_PATTERN'). In this case, \verb'L' is converted to the dtype of \verb'R'. The algorithm is described in \cite{DavisHager05}. %--------------------------------------- \subsection{{\tt cholmod\_rowadd\_solve}: add row to factor and update a solution} %--------------------------------------- \input{_rowadd_solve.tex} Identical to {\tt cholmod\_rowadd}, except the system $\m{Lx}=\m{b}$ is also updated/downdated, just like {\tt cholmod\_updown\_solve}. %--------------------------------------- \subsection{{\tt cholmod\_rowdel}: delete row from factor} %--------------------------------------- \input{_rowdel.tex} Deletes a row and column from an $\m{LDL}\tr$ factorization. The {\tt k}th row and column of {\tt L} is equal to the {\tt k}th row and column of the identity matrix on output. The dtypes of all matrices must match. Only real matrices are supported (double or single). %--------------------------------------- \subsection{{\tt cholmod\_rowdel\_solve}: delete row from factor and update a solution} %--------------------------------------- \input{_rowdel_solve.tex} Identical to {\tt cholmod\_rowdel}, except the system $\m{Lx}=\m{b}$ is also updated/downdated, just like {\tt cholmod\_updown\_solve}. When row/column $k$ of $\m{A}$ is deleted from the system $\m{Ay}=\m{b}$, this can induce a change to $\m{x}$, in addition to changes arising when $\m{L}$ and $\m{b}$ are modified. If this is the case, the kth entry of $\m{y}$ is required as input ({\tt yk}). The algorithm is described in \cite{DavisHager05}. %------------------------------------------------------------------------------- \newpage \section{{\tt MatrixOps} Module routines} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_drop}: drop small entries} %--------------------------------------- \input{_drop.tex} Drop small entries from {\tt A}, and entries in the ignored part of {\tt A} if {\tt A} is symmetric. No CHOLMOD routine drops small numerical entries from a matrix, except for this one. NaN's and Inf's are kept. %--------------------------------------- \subsection{{\tt cholmod\_norm\_dense}: dense matrix norm} %--------------------------------------- \input{_norm_dense.tex} Returns the infinity-norm, 1-norm, or 2-norm of a dense matrix. Can compute the 2-norm only for a dense column vector. %--------------------------------------- \subsection{{\tt cholmod\_norm\_sparse}: sparse matrix norm} %--------------------------------------- \input{_norm_sparse.tex} Returns the infinity-norm or 1-norm of a sparse matrix. %--------------------------------------- \subsection{{\tt cholmod\_scale}: scale sparse matrix} %--------------------------------------- \input{_scale.tex} Scales a matrix: {\tt A = diag(s)*A}, {\tt A*diag(s)}, {\tt s*A}, or {\tt diag(s)*A*diag(s)}. {\tt A} can be of any type (packed/unpacked, upper/lower/unsymmetric). The symmetry of {\tt A} is ignored; all entries in the matrix are modified. If {\tt A} is {\tt m}-by-{\tt n} unsymmetric but scaled symmetrically, the result is \begin{verbatim} A = diag (s (1:m)) * A * diag (s (1:n)) \end{verbatim} Row or column scaling of a symmetric matrix still results in a symmetric matrix, since entries are still ignored by other routines. For example, when row-scaling a symmetric matrix where just the upper triangular part is stored (and lower triangular entries ignored) {\tt A = diag(s)*triu(A)} is performed, where the result {\tt A} is also symmetric-upper. This has the effect of modifying the implicit lower triangular part. In MATLAB notation: \begin{verbatim} U = diag(s)*triu(A) ; L = tril (U',-1) A = L + U ; \end{verbatim} The scale parameter determines the kind of scaling to perform and the size of {\tt S}: \begin{tabular}{lll} \hline {\tt scale} & operation & size of {\tt S} \\ \hline {\tt CHOLMOD\_SCALAR} & {\tt s[0]*A} & 1 \\ {\tt CHOLMOD\_ROW} & {\tt diag(s)*A} & {\tt nrow}-by-1 or 1-by-{\tt nrow} \\ {\tt CHOLMOD\_COL} & {\tt A*diag(s)} & {\tt ncol}-by-1 or 1-by-{\tt ncol} \\ {\tt CHOLMOD\_SYM} & {\tt diag(s)*A*diag(s)} & {\tt max(nrow,ncol)}-by-1, or 1-by-{\tt max(nrow,ncol)} \\ \hline \end{tabular} %--------------------------------------- \subsection{{\tt cholmod\_sdmult}: sparse-times-dense matrix} %--------------------------------------- \input{_sdmult.tex} Sparse matrix times dense matrix: {\tt Y = alpha*(A*X) + beta*Y} or {\tt Y = alpha*(A'*X) + beta*Y}, where {\tt A} is sparse and {\tt X} and {\tt Y} are dense. When using {\tt A}, {\tt X} has {\tt A->ncol} rows and {\tt Y} has {\tt A->nrow} rows. When using {\tt A'}, {\tt X} has {\tt A->nrow} rows and {\tt Y} has {\tt A->ncol} rows. If {\tt transpose = 0}, then {\tt A} is used; otherwise, {\tt A'} is used (the complex conjugate transpose). The {\tt transpose} parameter is ignored if the matrix is symmetric or Hermitian. Supports real, complex, and zomplex matrices, but the xtypes and dtypes of {\tt A}, {\tt X}, and {\tt Y} must all match. %--------------------------------------- \subsection{{\tt cholmod\_ssmult}: sparse-times-sparse matrix} %--------------------------------------- \input{_ssmult.tex} Computes {\tt C = A*B}; multiplying two sparse matrices. {\tt C} is returned as packed, and either unsorted or sorted, depending on the {\tt sorted} input parameter. If {\tt C} is returned sorted, then either {\tt C = (B'*A')'} or {\tt C = (A*B)''} is computed, depending on the number of nonzeros in {\tt A}, {\tt B}, and {\tt C}. The stype of {\tt C} is determined by the {\tt stype} parameter. The xtypes and dtypes of \verb'A' and \verb'B' must match, unless \verb'mode' is 0. % If \verb'A' and/or \verb'B' are symmetric, a temporary unsymmetric copy is made, and the conversion is controlled by the \verb'mode' parameter. %--------------------------------------- \subsection{{\tt cholmod\_submatrix}: sparse submatrix} %--------------------------------------- \input{_submatrix.tex} Returns {\tt C = A (rset,cset)}, where {\tt C} becomes {\tt length(rset)}-by-{\tt length(cset)} in dimension. {\tt rset} and {\tt cset} can have duplicate entries. {\tt A} must be unsymmetric. {\tt C} unsymmetric and is packed. If {\tt sorted} is {\tt TRUE} on input, or {\tt rset} is sorted and {\tt A} is sorted, then {\tt C} is sorted; otherwise {\tt C} is unsorted. % If \verb'A' and/or \verb'B' are symmetric, a temporary unsymmetric copy is made, and the conversion is controlled by the \verb'mode' parameter. If {\tt rset} is {\tt NULL}, it means ``{\tt [ ]}'' in MATLAB notation, the empty set. The number of rows in the result {\tt C} will be zero if {\tt rset} is {\tt NULL}. Likewise if {\tt cset} means the empty set; the number of columns in the result {\tt C} will be zero if {\tt cset} is {\tt NULL}. If {\tt rsize} or {\tt csize} is negative, it denotes ``{\tt :}'' in MATLAB notation. Thus, if both {\tt rsize} and {\tt csize} are negative {\tt C = A(:,:) = A} is returned. For permuting a matrix, this routine is an alternative to {\tt cholmod\_ptranspose} (which permutes and transposes a matrix and can work on symmetric matrices). The time taken by this routine is O({\tt A->nrow}) if the {\tt Common} workspace needs to be initialized, plus O({\tt C->nrow + C->ncol + nnz (A (:,cset))}). Thus, if {\tt C} is small and the workspace is not initialized, the time can be dominated by the call to {\tt cholmod\_allocate\_work}. However, once the workspace is allocated, subsequent calls take less time. %--------------------------------------- \subsection{{\tt cholmod\_horzcat}: horizontal concatenation} %--------------------------------------- \input{_horzcat.tex} Horizontal concatenation, returns {\tt C = [A,B]} in MATLAB notation. {\tt A} and {\tt B} can have any stype. {\tt C} is returned unsymmetric and packed. {\tt A} and {\tt B} must have the same number of rows. {\tt C} is sorted if both {\tt A} and {\tt B} are sorted. {\tt A} and {\tt B} must have the same xtype and dtype, unless {\tt mode} is 0. % If \verb'A' and/or \verb'B' are symmetric, a temporary unsymmetric copy is made, and the conversion is controlled by the \verb'mode' parameter. %--------------------------------------- \subsection{{\tt cholmod\_vertcat}: vertical concatenation} %--------------------------------------- \input{_vertcat.tex} Vertical concatenation, returns {\tt C = [A;B]} in MATLAB notation. {\tt A} and {\tt B} can have any stype. {\tt C} is returned unsymmetric and packed. {\tt A} and {\tt B} must have the same number of columns. {\tt C} is sorted if both {\tt A} and {\tt B} are sorted. {\tt A} and {\tt B} must have the same xtype and dtype, unless {\tt mode} is 0. % If \verb'A' and/or \verb'B' are symmetric, a temporary unsymmetric copy is made, and the conversion is controlled by the \verb'mode' parameter. %--------------------------------------- \subsection{{\tt cholmod\_symmetry}: compute the symmetry of a matrix} %--------------------------------------- \input{_symmetry.tex} Determines if a sparse matrix is rectangular, unsymmetric, symmetric, skew-symmetric, or Hermitian. It does so by looking at its numerical values of both upper and lower triangular parts of a CHOLMOD "unsymmetric" matrix, where \verb'A->stype' == 0. The transpose of A is NOT constructed. If not unsymmetric, it also determines if the matrix has a diagonal whose entries are all real and positive (and thus a candidate for sparse Cholesky if \verb'A->stype' is changed to a nonzero value). Note that a Matrix Market "general" matrix is either rectangular or unsymmetric. The row indices in the column of each matrix MUST be sorted for this function to work properly (A->sorted must be TRUE). This routine returns EMPTY if A->stype is not zero, or if A->sorted is FALSE. The exception to this rule is if A is rectangular. If option == 0, then this routine returns immediately when it finds a non-positive diagonal entry (or one with nonzero imaginary part). If the matrix is not a candidate for sparse Cholesky, it returns the value {\tt CHOLMOD\_MM\_UNSYMMETRIC}, even if the matrix might in fact be symmetric or Hermitian. This routine is useful inside the MATLAB backslash, which must look at an arbitrary matrix (\verb'A->stype' == 0) and determine if it is a candidate for sparse Cholesky. In that case, option should be 0. This routine is also useful when writing a MATLAB matrix to a file in Rutherford/Boeing or Matrix Market format. Those formats require a determination as to the symmetry of the matrix, and thus this routine should not return upon encountering the first non-positive diagonal. In this case, option should be 1. If option is 2, this function can be used to compute the numerical and pattern symmetry, where 0 is a completely unsymmetric matrix, and 1 is a perfectly symmetric matrix. This option is used when computing the following statistics for the matrices in the SuiteSparse Matrix Collection. \begin{itemize} \item {\bf numerical symmetry}: number of matched off-diagonal nonzeros over the total number of off-diagonal entries. A real entry $a_{ij}$, $i \ne j$, is matched if $a_{ji} = a_{ij}$, but this is only counted if both $a_{ji}$ and $a_{ij}$ are nonzero. This does not depend on {\tt Z}. (If A is complex, then the above test is modified; $a_{ij}$ is matched if $\mbox{conj}(a_{ji}) = a_{ij}$). Then numeric symmetry = xmatched / nzoffdiag, or 1 if nzoffdiag = 0. \item {\bf pattern symmetry}: number of matched offdiagonal entries over the total number of offdiagonal entries. An entry $a_{ij}$, $i \ne j$, is matched if $a_{ji}$ is also an entry. Then pattern symmetry = pmatched / nzoffdiag, or 1 if nzoffdiag = 0. \end{itemize} The symmetry of a matrix with no offdiagonal entries is equal to 1. Summary of return values: \begin{tabular}{ll} {\tt EMPTY (-1)} & out of memory, stype not zero, A not sorted \\ {\tt CHOLMOD\_MM\_RECTANGULAR 1} & A is rectangular \\ {\tt CHOLMOD\_MM\_UNSYMMETRIC 2} & A is unsymmetric \\ {\tt CHOLMOD\_MM\_SYMMETRIC 3} & A is symmetric, but with non-pos. diagonal \\ {\tt CHOLMOD\_MM\_HERMITIAN 4} & A is Hermitian, but with non-pos. diagonal \\ {\tt CHOLMOD\_MM\_SKEW\_SYMMETRIC 5} & A is skew symmetric \\ {\tt CHOLMOD\_MM\_SYMMETRIC\_POSDIAG 6} & A is symmetric with positive diagonal \\ {\tt CHOLMOD\_MM\_HERMITIAN\_POSDIAG 7} & A is Hermitian with positive diagonal \\ \end{tabular} See also the {\tt spsym} mexFunction, which is a MATLAB interface for this code. If the matrix is a candidate for sparse Cholesky, it will return a result \newline {\tt CHOLMOD\_MM\_SYMMETRIC\_POSDIAG} if real, or {\tt CHOLMOD\_MM\_HERMITIAN\_POSDIAG} if complex. Otherwise, it will return a value less than this. This is true regardless of the value of the option parameter. %------------------------------------------------------------------------------- \newpage \section{{\tt Supernodal} Module routines} %------------------------------------------------------------------------------- Normally these methods are not called directly, but are accessed via the \verb'cholmod_analyze', \verb'cholmod_factorize', and \verb'cholmod_solve' methods. %--------------------------------------- \subsection{{\tt cholmod\_super\_symbolic}: supernodal symbolic factorization} %--------------------------------------- \input{_super_symbolic.tex} Supernodal symbolic analysis of the $\m{LL}\tr$ factorization of {\tt A}, {\tt A*A'}, or {\tt A(:,f)*A(:,f)'}. This routine must be preceded by a simplicial symbolic analysis ({\tt cholmod\_rowcolcounts}). See {\tt Cholesky/cholmod\_analyze.c} for an example of how to use this routine. The user need not call this directly; {\tt cholmod\_analyze} is a ``simple'' wrapper for this routine. {\tt A} can be symmetric (upper), or unsymmetric. The symmetric/lower form is not supported. In the unsymmetric case {\tt F} is the normally transpose of {\tt A}. Alternatively, if {\tt F=A(:,f)'} then {\tt F*F'} is analyzed. Requires {\tt Parent} and {\tt L->ColCount} to be defined on input; these are the simplicial {\tt Parent} and {\tt ColCount} arrays as computed by {\tt cholmod\_rowcolcounts}. Does not use {\tt L->Perm}; the input matrices {\tt A} and {\tt F} must already be properly permuted. Allocates and computes the supernodal pattern of {\tt L} ({\tt L->super}, {\tt L->pi}, {\tt L->px}, and {\tt L->s}). Does not allocate the real part ({\tt L->x}). %--------------------------------------- \subsection{{\tt cholmod\_super\_numeric}: supernodal numeric factorization} %--------------------------------------- \input{_super_numeric.tex} Computes the numerical Cholesky factorization of {\tt A+beta*I} or {\tt A*F+beta*I}. Only the lower triangular part of {\tt A+beta*I} or {\tt A*F+beta*I} is accessed. The matrices {\tt A} and {\tt F} must already be permuted according to the fill-reduction permutation {\tt L->Perm}. {\tt cholmod\_factorize} is an "easy" wrapper for this code which applies that permutation. The input scalar {\tt beta} is real; only the real part ({\tt beta[0]}) is used. Symmetric case: {\tt A} is a symmetric (lower) matrix. {\tt F} is not accessed and may be {\tt NULL}. With a fill-reducing permutation, {\tt A(p,p)} should be passed for {\tt A}, where is {\tt p} is {\tt L->Perm}. Unsymmetric case: {\tt A} is unsymmetric, and {\tt F} must be present. Normally, {\tt F=A'}. With a fill-reducing permutation, {\tt A(p,f)} and {\tt A(p,f)'} should be passed as the parameters {\tt A} and {\tt F}, respectively, where {\tt f} is a list of the subset of the columns of {\tt A}. The input factorization {\tt L} must be supernodal ({\tt L->is\_super} is {\tt TRUE}). It can either be symbolic or numeric. In the first case, {\tt L} has been analyzed by {\tt cholmod\_analyze} or {\tt cholmod\_super\_symbolic}, but the matrix has not yet been numerically factorized. The numerical values are allocated here and the factorization is computed. In the second case, a prior matrix has been analyzed and numerically factorized, and a new matrix is being factorized. The numerical values of {\tt L} are replaced with the new numerical factorization. {\tt L->is\_ll} is ignored on input, and set to {\tt TRUE} on output. This routine always computes an $\m{LL}\tr$ factorization. Supernodal $\m{LDL}\tr$ factorization is not supported. If the matrix is not positive definite the routine returns {\tt TRUE}, but sets {\tt Common->status} to {\tt CHOLMOD\_NOT\_POSDEF} and {\tt L->minor} is set to the column at which the failure occurred. Columns {\tt L->minor} to {\tt L->n-1} are set to zero. If {\tt L} is supernodal symbolic on input, it is converted to a supernodal numeric factor on output, with an xtype of real if {\tt A} is real, or complex if {\tt A} is complex or zomplex. If {\tt L} is supernodal numeric on input, its xtype must match {\tt A} (except that {\tt L} can be complex and {\tt A} zomplex). The xtype of {\tt A} and {\tt F} must match. %--------------------------------------- \subsection{{\tt cholmod\_super\_lsolve}: supernodal forward solve} %--------------------------------------- \input{_super_lsolve.tex} Solve $\m{Lx}=\m{b}$ for a supernodal factorization. This routine does not apply the permutation {\tt L->Perm}. See {\tt cholmod\_solve} for a more general interface that performs that operation. Only real and complex xtypes are supported. {\tt L}, {\tt X}, and {\tt E} must have the same xtype. %--------------------------------------- \subsection{{\tt cholmod\_super\_ltsolve}: supernodal backsolve} %--------------------------------------- \input{_super_ltsolve.tex} Solve $\m{L}\tr\m{x}=\m{b}$ for a supernodal factorization. This routine does not apply the permutation {\tt L->Perm}. See {\tt cholmod\_solve} for a more general interface that performs that operation. Only real and complex xtypes are supported. {\tt L}, {\tt X}, and {\tt E} must have the same xtype. %------------------------------------------------------------------------------- \newpage \section{{\tt Partition} Module routines} %------------------------------------------------------------------------------- %--------------------------------------- \subsection{{\tt cholmod\_nested\_dissection}: nested dissection ordering} %--------------------------------------- \input{_nested_dissection.tex} CHOLMOD's nested dissection algorithm: using its own compression and connected-components algorithms, an external graph partitioner (METIS), and a constrained minimum degree ordering algorithm (CAMD, CCOLAMD, or CSYMAMD). Typically gives better orderings than {\tt METIS\_NodeND} (about 5\% to 10\% fewer nonzeros in {\tt L}). This method uses a node bisector, applied recursively (but using a non-recursive implementation). Once the graph is partitioned, it calls a constrained minimum degree code (CAMD or CSYMAMD for {\tt A+A'}, and CCOLAMD for {\tt A*A'}) to order all the nodes in the graph - but obeying the constraints determined by the separators. This routine is similar to {\tt METIS\_NodeND}, except for how it treats the leaf nodes. {\tt METIS\_NodeND} orders the leaves of the separator tree with {\tt MMD}, ignoring the rest of the matrix when ordering a single leaf. This routine orders the whole matrix with CAMD, CSYMAMD, or CCOLAMD, all at once, when the graph partitioning is done. %--------------------------------------- \subsection{{\tt cholmod\_metis}: interface to METIS nested dissection} %--------------------------------------- \input{_metis.tex} CHOLMOD wrapper for the {\tt METIS\_NodeND} ordering routine. Creates {\tt A+A'}, {\tt A*A'} or {\tt A(:,f)*A(:,f)'} and then calls {\tt METIS\_NodeND} on the resulting graph. This routine is comparable to {\tt cholmod\_nested\_dissection}, except that it calls {\tt METIS\_NodeND} directly, and it does not return the separator tree. %--------------------------------------- \subsection{{\tt cholmod\_camd}: interface to CAMD} %--------------------------------------- \input{_camd.tex} CHOLMOD interface to the CAMD ordering routine. Finds a permutation {\tt p} such that the Cholesky factorization of {\tt A(p,p)} is sparser than {\tt A}. If {\tt A} is unsymmetric, {\tt A*A'} is ordered. If {\tt Cmember[i]=c} then node {\tt i} is in set {\tt c}. All nodes in set 0 are ordered first, followed by all nodes in set 1, and so on. %--------------------------------------- \subsection{{\tt cholmod\_ccolamd}: interface to CCOLAMD} %--------------------------------------- \input{_ccolamd.tex} CHOLMOD interface to the CCOLAMD ordering routine. Finds a permutation {\tt p} such that the Cholesky factorization of {\tt A(p,:)*A(p,:)'} is sparser than {\tt A*A'}. The column elimination is found and postordered, and the CCOLAMD ordering is then combined with its postordering. {\tt A} must be unsymmetric. If {\tt Cmember[i]=c} then node {\tt i} is in set {\tt c}. All nodes in set 0 are ordered first, followed by all nodes in set 1, and so on. %--------------------------------------- \subsection{{\tt cholmod\_csymamd}: interface to CSYMAMD} %--------------------------------------- \input{_csymamd.tex} CHOLMOD interface to the CSYMAMD ordering routine. Finds a permutation {\tt p} such that the Cholesky factorization of {\tt A(p,p)} is sparser than {\tt A}. The elimination tree is found and postordered, and the CSYMAMD ordering is then combined with its postordering. If {\tt A} is unsymmetric, {\tt A+A'} is ordered ({\tt A} must be square). If {\tt Cmember[i]=c} then node {\tt i} is in set {\tt c}. All nodes in set 0 are ordered first, followed by all nodes in set 1, and so on. %--------------------------------------- \subsection{{\tt cholmod\_bisect}: graph bisector} %--------------------------------------- \input{_bisect.tex} Finds a node bisector of {\tt A}, {\tt A*A'}, {\tt A(:,f)*A(:,f)'}: a set of nodes that partitions the graph into two parts. Compresses the graph first, ensures the graph is symmetric with no diagonal entries, and then calls METIS. %--------------------------------------- \subsection{{\tt cholmod\_metis\_bisector}: interface to METIS node bisector} %--------------------------------------- \input{_metis_bisector.tex} Finds a set of nodes that bisects the graph of {\tt A} or {\tt A*A'} (a direct interface to \newline {\tt METIS\_NodeComputeSeparator}). The input matrix {\tt A} must be square, symmetric (with both upper and lower parts present) and with no diagonal entries. These conditions are not checked. Use {\tt cholmod\_bisect} to check these conditions. %--------------------------------------- \subsection{{\tt cholmod\_collapse\_septree}: prune a separator tree} %--------------------------------------- \input{_collapse_septree.tex} Prunes a separator tree obtained from {\tt cholmod\_nested\_dissection}. \newpage \bibliographystyle{plain} \bibliography{UserGuide} \end{document}