scilab/modules/sparse/help/ja_JP/ordmmd.xml

   1 <?xml version="1.0" encoding="UTF-8"?>
   2 <!--
   3  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
   4  * Copyright (C) 2011 - DIGITEO - Michael Baudin
   5  *
   6  * This file must be used under the terms of the CeCILL.
   7  * This source file is licensed as described in the file COPYING, which
   8  * you should have received as part of this distribution.  The terms
   9  * are also available at
  10  * http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt
  11  *
  12  -->
  13 <refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ns5="http://www.w3.org/1999/xhtml" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook" xmlns:scilab="http://www.scilab.org" xml:id="ordmmd" xml:lang="ja">
  14     <refnamediv>
  15         <refname>ordmmd</refname>
  16         <refpurpose>
  17             複数の最小次元規則配列を計算する
  18         </refpurpose>
  19     </refnamediv>
  20     <refsynopsisdiv>
  21         <title>呼び出し手順</title>
  22         <synopsis>
  23             [perm,invp,nofsub]=ordmmd(xadj,iadj,n)
  24         </synopsis>
  25     </refsynopsisdiv>
  26     <refsection>
  27         <title>引数</title>
  28         <variablelist>
  29             <varlistentry>
  30                 <term>n</term>
  31                 <listitem>
  32                     <para>double、整数値の1行1列の行列,方程式の数</para>
  33                 </listitem>
  34             </varlistentry>
  35             <varlistentry>
  36                 <term>xadj</term>
  37                 <listitem>
  38                     <para>double、整数値の(n+1)行1列の行列,Aの行へのポインタ</para>
  39                 </listitem>
  40             </varlistentry>
  41             <varlistentry>
  42                 <term>iadj</term>
  43                 <listitem>
  44                     <para>double、整数値のnnz行1列の行列,Aの行添字</para>
  45                 </listitem>
  46             </varlistentry>
  47             <varlistentry>
  48                 <term>perm</term>
  49                 <listitem>
  50                     <para>double、整数値のn行1列の行列,最小次元規則配列</para>
  51                 </listitem>
  52             </varlistentry>
  53             <varlistentry>
  54                 <term>invp</term>
  55                 <listitem>
  56                     <para>double、整数値のn行1列の行列,permの逆行列</para>
  57                 </listitem>
  58             </varlistentry>
  59             <varlistentry>
  60                 <term>nofsub</term>
  61                 <listitem>
  62                     <para>
  63                         double、整数値の1行1列の行列,圧縮記憶方式における非ゼロ要素の数の上限
  64                     </para>
  65                 </listitem>
  66             </varlistentry>
  67         </variablelist>
  68     </refsection>
  69     <refsection>
  70         <title>説明</title>
  71         <para>
  72             コレスキー分解を適用する前に対称疎行列の行および列を交換する際に最小次元アルゴリズムが使用されます.
  73             このアルゴリズムはコレスキー分解の非ゼロ要素の数を減らします.
  74         </para>
  75         <para>
  76             n行n列の実対称疎行列<literal>A</literal>を指定すると,
  77             このコレスキー分解 <literal>U</literal> は,通常,
  78             <literal>A</literal>の上三角要素よりも非ゼロ要素が多くなる
  79             "塗りつぶし(fill in)"に苦しめられます.
  80             行列<literal>P'*A*P</literal>が同じく対称で,そのコレスキー分解の非ゼロ要素の数が最小となる
  81             交換行列 <literal>P</literal>を探します.
  82         </para>
  83     </refsection>
  84     <refsection>
  85         <title>例</title>
  86         <para>
  87             以下の例では,対称疎行列の規則配列を計算します.
  88             隣接構造体を計算する際に<literal>sp2adj</literal> を使用します.
  89         </para>
  90         <programlisting role="example"><![CDATA[
  91 A = [
  92 4. 1. 2. 0.5 2.
  93 1. 0.5 0. 0. 0.
  94 2. 0. 3. 0. 0.
  95 0.5 0. 0. 5./8. 0.
  96 2. 0. 0. 0. 16.
  97 ];
  98 A = sparse(A);
  99 [xadj,iadj,val]=sp2adj(A);
 100 n = size(A,"r");
 101 [perm,invp,nofsub]=ordmmd(xadj,iadj,n)
 102  ]]></programlisting>
 103         <para>
 104             以下の例では,対称疎行列の規則配列を計算します.
 105             <literal>invp</literal>が<literal>perm</literal>の逆行列であることを確認します.
 106         </para>
 107         <programlisting role="example"><![CDATA[
 108     A = [
 109     0.,  0.,  0.,  2.,  0.,  0.,  2.,  0.,  2.,  0.,  0. ;
 110     0.,  0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0. ;
 111     0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0. ;
 112     2.,  0.,  0.,  0.,  0.,  0.,  2.,  0.,  2.,  0.,  0. ;
 113     0.,  0.,  0.,  0. , 0.,  0.,  0.,  0.,  0.,  0.,  4. ;
 114     0.,  0.,  0.,  0.,  0.,  0.,  0.,  3.,  0.,  3.,  0. ;
 115     2.,  0.,  0.,  2.,  0.,  0.,  0.,  0.,  2.,  0.,  0. ;
 116     0.,  0.,  0.,  0.,  0.,  3.,  0.,  0.,  0.,  3.,  0. ;
 117     2.,  0.,  0.,  2.,  0.,  0.,  2.,  0.,  0.,  0.,  0. ;
 118     0.,  0.,  0.,  0.,  0.,  3.,  0.,  3.,  0.,  0.,  0. ;
 119     0.,  0.,  0.,  0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.];
 120     n=size(A,1);
 121     A=sparse(A);
 122     [xadj,adjncy,anz]=sp2adj(A);
 123     [perm,invp,nofsub]=ordmmd(xadj,adjncy,n);
 124     perm(invp)
 125  ]]></programlisting>
 126         <para>
 127             以下の例では, 行列<literal>A</literal>と行列<literal>P'*A*P</literal>
 128             のコレスキー分解の疎パターンを計算します.
 129             "Computer Solution of Large Sparse Positive Definite Systems"のp.3 "Chapter 1: Introduction"を参照.
 130             コレスキー分解の非ゼロ要素の数は15,一方,行列<literal>P'*A*P</literal>のコレスキー分解は
 131             9個の非ゼロ要素を有することがわかります.
 132         </para>
 133         <programlisting role="example"><![CDATA[
 134 A = [
 135 4. 1. 2. 0.5 2.
 136 1. 0.5 0. 0. 0.
 137 2. 0. 3. 0. 0.
 138 0.5 0. 0. 5./8. 0.
 139 2. 0. 0. 0. 16.
 140 ];
 141 A = sparse(A);
 142 // Aのコレスキー分解の疎パターンを調べる
 143 U = sparse(chol(full(A)));
 144 scf();
 145 subplot(2,1,1);
 146 PlotSparse(U,"x");
 147 xtitle("Sparsity pattern of U, such that A=U''*U");
 148 // 隣接構造体を取得
 149 [xadj,iadj,val]=sp2adj(A);
 150 // 複数の最小次元規則配列を計算
 151 n = size(A,"r");
 152 [perm,invp,nofsub]=ordmmd(xadj,iadj,n);
 153 // 交換ベクトルを行列に変換
 154 P=spzeros(n,n);
 155 for i=1:n
 156     P(perm(i),i)=1;
 157 end
 158 // P'*A*Pのコレスキー分解の疎パターンを調べる
 159 U = sparse(chol(full(P'*A*P)));
 160 subplot(2,1,2);
 161 PlotSparse(U,"x");
 162 xtitle("Sparsity pattern of U, such that P''*A*P=U''*U");
 163  ]]></programlisting>
 164     </refsection>
 165     <refsection>
 166         <title>実装に関する注記</title>
 167         <para>
 168             この関数はMathematical Sciences Section, Oak Ridge National Laboratoryの
 169             Esmond G. Ng および Barry W. Peytonによる
 170             ソースコード "ordmmd.f",に基づいています.
 171             アルゴリズムはSPARSPAKライブラリのJoseph W.H. Liuによる genmmdルーチンに基づいています.
 172         </para>
 173     </refsection>
 174     <refsection>
 175         <title>参考文献</title>
 176         <para>
 177             "Minimum degree algorithm", Wikipedia contributors, Wikipedia, The Free Encyclopedia. http://en.wikipedia.org/wiki/Minimum_degree_algorithm
 178         </para>
 179         <para>
 180             "A new release of SPARSPAK: the Waterloo sparse matrix package", Alan George and Esmond Ng. 1984. SIGNUM Newsl. 19, 4 (October 1984), 9-13.
 181         </para>
 182         <para>
 183             "Computer Solution of Large Sparse Positive Definite Systems" by Alan George and Joseph Liu, Prentice-Hall, Inc. Englewood Cliffs, New Jersey, 1981
 184         </para>
 185         <para>
 186             "Implementation of Lipsol in Scilab", Rubio Scola, 1997, INRIA, No 0215
 187         </para>
 188     </refsection>
 189     <refsection role="see also">
 190         <title>参照</title>
 191         <simplelist type="inline">
 192             <member>
 193                 <link linkend="sp2adj">sp2adj</link>
 194             </member>
 195             <member>
 196                 <link linkend="spchol">spchol</link>
 197             </member>
 198         </simplelist>
 199     </refsection>
 200 </refentry>