# HG changeset patch # User Nir Krakauer and Rik # Date 1414887863 25200 # Node ID 76a6ba7d65d04ec75f33aa6b5ce1cabffee83d3e # Parent b80b396e7d54d2d7e2f2d3b6f5d33a1c5173ad19 doc: Update documentation for ilu, ichol. * ichol.m, ilu.m: Clarify options available for factorization. diff -r b80b396e7d54 -r 76a6ba7d65d0 scripts/sparse/ichol.m --- a/scripts/sparse/ichol.m Thu Oct 30 17:49:58 2014 -0700 +++ b/scripts/sparse/ichol.m Sat Nov 01 17:24:23 2014 -0700 @@ -1,6 +1,6 @@ ## Copyright (C) 2014 Eduardo Ramos Fernández ## Copyright (C) 2013 Kai T. Ohlhus -## +## ## This file is part of Octave. ## ## Octave is free software; you can redistribute it and/or modify it @@ -22,67 +22,75 @@ ## @deftypefnx {Function File} {@var{L} =} ichol (@var{A}, @var{opts}) ## ## Compute the incomplete Cholesky factorization of the sparse square matrix -## @var{A} with zero-fill. +## @var{A}. ## -## By default, ichol references the lower triangle of @var{A} and produces -## lower triangular factors. +## By default, @code{ichol} uses only the lower triangle of @var{A} and +## produces a lower triangular factor @var{L} such that @tcode{L*L'} +## approximates @var{A}. ## ## The factor given by this routine may be useful as a preconditioner for a ## system of linear equations being solved by iterative methods such as ## PCG (Preconditioned Conjugate Gradient). ## ## The factorization may be modified by passing options in a structure -## @var{opts}. The option name is a field in the structure and the setting +## @var{opts}. The option name is a field of the structure and the setting ## is the value of field. Names and specifiers are case sensitive. ## ## @table @asis ## @item type ## Type of factorization. -## String indicating which flavor of incomplete Cholesky to perform. Valid -## values of this field are @qcode{"nofill"} and @qcode{"ict"}. The -## @qcode{"nofill"} variant performs incomplete Cholesky with zero-fill -## @nospell{[IC(0)]}. The @qcode{"ict"} variant performs incomplete Cholesky -## with threshold dropping @nospell{[ICT]}. The default value is -## @qcode{"nofill"}. +## +## @table @asis +## @item @qcode{"nofill"} (default) +## Incomplete Cholesky factorization with no fill-in (@nospell{IC(0)}). +## +## @item @qcode{"ict"} +## Incomplete Cholesky factorization with threshold dropping (@nospell{ICT}). +## @end table +## +## @item diagcomp +## A non-negative scalar @var{alpha} for incomplete Cholesky factorization of +## @code{@var{A} + @var{alpha} * diag (diag (@var{A}))} instead of @var{A}. +## This can be useful when @var{A} is not positive definite. The default value +## is 0. ## ## @item droptol -## Drop tolerance when type is @qcode{"ict"}. -## Non-negative scalar used as a drop tolerance when performing @nospell{ICT}@. -## Elements which are smaller in magnitude than a local drop tolerance are -## dropped from the resulting factor except for the diagonal element which is -## never dropped. -## The local drop tolerance at step j of the factorization is -## @code{norm (@var{A}(j:end, j), 1) * droptol}. @code{droptol} is ignored if -## @code{type} is @qcode{"nofill"}. The default value is 0. +## A non-negative scalar specifying the drop tolerance for factorization if +## performing @nospell{ICT}@. The default value is 0 which produces the complete +## Cholesky factorization. +## +## Non-diagonal entries of @var{L} are set to 0 unless +## +## @code{abs (@var{L}(i,j)) >= droptol * norm (@var{A}(j:end, j), 1)}. ## ## @item michol -## Indicate whether modified incomplete Cholesky [MIC] is performed. -## The field may be @qcode{"on"} or @qcode{"off"}. When performing MIC, the -## diagonal is compensated for dropped elements to enforce the relationship -## @code{@var{A} * @var{e} = @var{L} * @var{L}' * @var{e}} where -## @code{@var{e} = ones (columns (@var{A}), 1)}. The default value is -## @qcode{"off"}. +## Modified incomplete Cholesky factorization: +## +## @table @asis +## @item @qcode{"off"} (default) +## Row and column sums are not necessarily preserved. ## -## @item diagcomp -## Perform compensated incomplete Cholesky with the specified coefficient. -## The coefficient is a real non-negative scalar used as a global diagonal -## shift @code{@var{alpha}} in forming the incomplete Cholesky factor. That -## is, instead of performing incomplete Cholesky on @code{@var{A}}, the -## factorization of @code{@var{A} + @var{alpha} * diag (diag (@var{A}))} is -## formed. The default value is 0. +## @item @qcode{"on"} +## The diagonal of @var{L} is modified so that row (and column) sums are +## preserved even when elements have been dropped during the factorization. +## The relationship preserved is: @code{@var{A} * e = @var{L} * @var{L}' * e}, +## where e is a vector of ones. +## @end table ## ## @item shape -## Determine which triangle is referenced and returned. -## Valid values are @qcode{"upper"} and @qcode{"lower"}. If @qcode{"upper"} -## is specified, only the upper triangle of @code{@var{A}} is referenced and -## @code{@var{R}} is constructed such that @code{@var{A}} is approximated by -## @code{@var{R}' * @var{R}}. If @qcode{"lower"} is specified, only the -## lower triangle of @code{@var{A}} is referenced and @code{@var{L}} is -## constructed such that @code{@var{A}} is approximated by @code{@var{L} * -## @var{L}'}. The default value is @qcode{"lower"}. +## +## @table @asis +## @item @qcode{"lower"} (default) +## Use only the lower triangle of @var{A} and return a lower triangular +## factor @var{L} such that @tcode{L*L'} approximates @var{A}. +## +## @item @qcode{"upper"} +## Use only the upper triangle of @var{A} and return an upper triangular +## factor @var{U} such that @code{U'*U} approximates @var{A}. +## @end table ## @end table ## -## Examples +## EXAMPLES ## ## The following problem demonstrates how to factorize a sample symmetric ## positive definite matrix with the full Cholesky decomposition and with the @@ -159,7 +167,7 @@ endif ## If A is empty then return empty L for Matlab compatibility - if (isempty (A)) + if (isempty (A)) L = A; return; endif @@ -237,7 +245,7 @@ if (strcmp (opts.shape, "upper")) L = L'; endif - + endfunction @@ -342,14 +350,14 @@ %! L = ichol (A5, opts); %! assert (norm (A5 - L*L', "fro") / norm (A5, "fro"), 0.0276, 1e-4); -## Negative pivot +## Negative pivot %!error ichol (A6) %!error ichol (A6) ## Complex entry in the diagonal %!error ichol (A7) ## ICHOLT tests - + %%!test %! opts.type = "ict"; %! opts.droptol = 1e-1; diff -r b80b396e7d54 -r 76a6ba7d65d0 scripts/sparse/ilu.m --- a/scripts/sparse/ilu.m Thu Oct 30 17:49:58 2014 -0700 +++ b/scripts/sparse/ilu.m Sat Nov 01 17:24:23 2014 -0700 @@ -18,113 +18,106 @@ ## . ## -*- texinfo -*- -## @deftypefn {Function File} {@var{L}, @var{U}] =} ilu (@var{A}) -## @deftypefnx {Function File} {@var{L}, @var{U}] =} ilu (@var{A}, @var{opts}) +## @deftypefn {Function File} {} ilu (@var{A}) +## @deftypefnx {Function File} {} ilu (@var{A}, @var{opts}) +## @deftypefnx {Function File} {[@var{L}, @var{U}] =} ilu (@dots{}) ## @deftypefnx {Function File} {[@var{L}, @var{U}, @var{P}] =} ilu (@dots{}) ## -## Compute the incomplete LU factorization of the sparse square matrix @var{A} -## into a unit lower triangular matrix (@var{L}), an upper triangular matrix -## (@var{U}), and a permutation matrix (@var{P}). +## Compute the incomplete LU factorization of the sparse square matrix @var{A}. ## -## These incomplete factorizations may be useful as preconditioners for a +## @code{ilu} returns a unit lower triangular matrix @var{L}, an upper +## triangular matrix @var{U}, and optionally a permutation matrix @var{P}, such +## that @code{@var{L}*@var{U}} approximates @code{@var{P}*@var{A}}. +## +## The factors given by this routine may be useful as preconditioners for a ## system of linear equations being solved by iterative methods such as BICG ## (BiConjugate Gradients) or GMRES (Generalized Minimum Residual Method). ## ## The factorization may be modified by passing options in a structure -## @var{opts}. The option name is a field in the structure and the setting +## @var{opts}. The option name is a field of the structure and the setting ## is the value of field. Names and specifiers are case sensitive. ## ## @table @code ## @item type -## Type of factorization. Values for type include: +## Type of factorization. ## ## @table @asis ## @item @qcode{"nofill"} -## Perform ILU factorization with 0 level of fill in, known as ILU(0). With -## type set to @qcode{"nofill"}, only the @code{milu} option is used; all other -## fields are ignored. +## ILU factorization with no fill-in (ILU(0)). +## +## Additional supported options: @code{milu}. ## ## @item @qcode{"crout"} -## Perform the @nospell{Crout} version of ILU factorization, known as -## @nospell{ILUC}@. With type set to @qcode{crout}, only the @code{droptol} -## and @code{milu} options are used; all other fields are ignored. +## Crout version of ILU factorization (@nospell{ILUC}). +## +## Additional supported options: @code{milu}, @code{droptol}. ## -## @item @qcode{"ilutp"} -## (default) Performs ILU factorization with threshold and pivoting. +## @item @qcode{"ilutp"} (default) +## ILU factorization with threshold and pivoting. +## +## Additional supported options: @code{milu}, @code{droptol}, @code{udiag}, +## @code{thresh}. ## @end table ## -## If type is not specified, the ILU factorization with pivoting @nospell{ILUTP} -## is performed. Pivoting is never performed with type set to @qcode{"nofill"} -## or @qcode{"crout"}. -## ## @item droptol -## Drop tolerance of the incomplete LU factorization. @code{droptol} is a -## non-negative scalar. The default value is 0, which produces the complete -## LU factorization. +## A non-negative scalar specifying the drop tolerance for factorization. The +## default value is 0 which produces the complete LU factorization. ## -## The nonzero entries of @var{U} satisfy -## -## @code{abs (@var{U}(i,j)) >= droptol * norm ((@var{A}:,j))} +## Non-diagonal entries of @var{U} are set to 0 unless ## -## with the exception of the diagonal entries, which are retained regardless of -## satisfying the criterion. The entries of @var{L} are tested against the -## local drop tolerance before being scaled by the pivot, so for nonzeros in -## @var{L} +## @code{abs (@var{U}(i,j)) >= droptol * norm (@var{A}(:,j))}. +## +## Non-diagonal entries of @var{L} are set to 0 unless ## ## @code{abs (@var{L}(i,j)) >= droptol * norm (@var{A}(:,j))/@var{U}(j,j)}. ## ## @item milu -## Modified incomplete LU factorization. Values for @code{milu} -## include: +## Modified incomplete LU factorization: ## ## @table @asis ## @item @qcode{"row"} -## Produces the row-sum modified incomplete LU factorization. Entries from the -## newly-formed column of the factors are subtracted from the diagonal of the -## upper triangular factor, @var{U}, preserving column sums. That is, -## @code{@var{A} * e = @var{L} * @var{U} * e}, where e is the vector of ones. +## Row-sum modified incomplete LU factorization. +## The factorization preserves row sums: +## @code{@var{A} * e = @var{L} * @var{U} * e}, where e is a vector of ones. ## ## @item @qcode{"col"} -## Produces the column-sum modified incomplete LU factorization. Entries from -## the newly-formed column of the factors are subtracted from the diagonal of -## the upper triangular factor, @var{U}, preserving column sums. That is, -## @code{e'*@var{A} = e'*@var{L}*@var{U}}. +## Column-sum modified incomplete LU factorization. +## The factorization preserves column sums: +## @code{e' * @var{A} = e' * @var{L} * @var{U}}. ## -## @item @qcode{"off"} -## (default) No modified incomplete LU factorization is produced. +## @item @qcode{"off"} (default) +## Row and column sums are not necessarily preserved. ## @end table ## ## @item udiag -## If @code{udiag} is 1, any zeros on the diagonal of the upper -## triangular factor are replaced by the local drop tolerance. The default -## is 0. +## If true, any zeros on the diagonal of the upper triangular factor are +## replaced by the local drop tolerance +## @code{droptol * norm (@var{A}(:,j))/@var{U}(j,j)}. The default is false. ## ## @item thresh -## Pivot threshold between 0 (forces diagonal pivoting) and 1, -## the default, which always chooses the maximum magnitude entry in the column -## to be the pivot. +## Pivot threshold for factorization. It can range between 0 (diagonal +## pivoting) and 1 (default), where the maximum magnitude entry in the column +## is chosen to be the pivot. ## @end table ## -## @code{ilu (@var{A},@var{setup})} returns -## @code{@var{L} + @var{U} - speye (size (@var{A}))}, where @var{L} is a unit -## lower triangular matrix and @var{U} is an upper triangular matrix. +## If @code{ilu} is called with just one output, the returned matrix is +## @code{@var{L} + @var{U} - speye (size (@var{A}))}, where @var{L} is unit +## lower triangular and @var{U} is upper triangular. ## -## @code{[@var{L}, @var{U}] = ilu (@var{A},@var{setup})} returns a unit lower -## triangular matrix in @var{L} and an upper triangular matrix in @var{U}. When -## SETUP.type = @qcode{"ilutp"}, the role of @var{P} is determined by the -## value of SETUP.milu. For SETUP.type == @qcode{"ilutp"}, one of the -## factors is permuted based on the value of SETUP.milu. When SETUP.milu == -## @qcode{"row"}, U is a column permuted upper triangular factor. Otherwise, -## L is a row-permuted unit lower triangular factor. +## With two outputs, @code{ilu} returns a unit lower triangular matrix @var{L} +## and an upper triangular matrix @var{U}. For @var{opts}.type == +## @qcode{"ilutp"}, one of the factors is permuted based on the value of +## @var{opts}.milu. When @var{opts}.milu == @qcode{"row"}, @var{U} is a +## column permuted upper triangular factor. Otherwise, @var{L} is a +## row-permuted unit lower triangular factor. ## -## @code{[@var{L}, @var{U}, @var{P}] = ilu (@var{A},@var{setup})} returns a -## unit lower triangular matrix in @var{L}, an upper triangular matrix in -## @var{U}, and a permutation matrix in @var{P}. When @code{milu} ! = -## @qcode{"row"}, @var{P} is returned such that @var{L} and @var{U} are -## incomplete factors of @var{P}*@var{A}. When @code{milu} == @qcode{"row"}, -## @var{P} is returned such that and @var{U} are incomplete factors of A*P. +## If there are three named outputs and @var{opts}.milu != @qcode{"row"}, +## @var{P} is returned such that @var{L} and @var{U} are incomplete factors +## of @code{@var{P}*@var{A}}. When @var{opts}.milu == @qcode{"row"}, @var{P} +## is returned such that @var{L} and @var{U} are incomplete factors of +## @code{@var{A}*@var{P}}. ## -## Examples +## EXAMPLES ## ## @example ## @group @@ -141,9 +134,9 @@ ## @end group ## @end example ## -## This shows that @var{A} has 7840 nonzeros, the complete LU factorization has -## 126478 nonzeros, and the incomplete LU factorization, with 0 level of -## fill-in, has 7840 nonzeros, the same amount as @var{A}. Taken from: +## This shows that @var{A} has 7,840 nonzeros, the complete LU factorization has +## 126,478 nonzeros, and the incomplete LU factorization, with 0 level of +## fill-in, has 7,840 nonzeros, the same amount as @var{A}. Taken from: ## http://www.mathworks.com/help/matlab/ref/ilu.html ## ## @example