translation updated for sparse.
[scilab.git] / scilab / modules / sparse / help / ja_JP / ordmmd.xml
1 <?xml version="1.0" encoding="UTF-8"?>
2
3 <!--
4  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
5  * Copyright (C) 2011 - DIGITEO - Michael Baudin
6  * 
7  * This file must be used under the terms of the CeCILL.
8  * This source file is licensed as described in the file COPYING, which
9  * you should have received as part of this distribution.  The terms
10  * are also available at    
11  * http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt
12  *
13  -->
14
15 <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">
16     
17     <refnamediv>
18         
19         <refname>ordmmd</refname>
20         
21         <refpurpose>
22             
23             複数の最小次元順序付けを計算する
24             
25         </refpurpose>
26         
27     </refnamediv>
28     
29     <refsynopsisdiv>
30         
31         <title>呼び出し手順</title>
32         
33         <synopsis>
34             
35             [perm,invp,nofsub]=ordmmd(xadj,iadj,n)
36             
37         </synopsis>
38         
39     </refsynopsisdiv>
40     
41     <refsection>
42         
43         <title>引数</title>
44         
45         <variablelist>
46             
47             <varlistentry>
48                 
49                 <term>n</term>
50                 
51                 <listitem>
52                     
53                     <para>double、整数値の1行1列の行列,方程式の数</para>
54                     
55                 </listitem>
56                 
57             </varlistentry>
58             
59             <varlistentry>
60                 
61                 <term>xadj</term>
62                 
63                 <listitem>
64                     
65                     <para>double、整数値の(n+1)行1列の行列,Aの行へのポインタ</para>
66                     
67                 </listitem>
68                 
69             </varlistentry>
70             
71             <varlistentry>
72                 
73                 <term>iadj</term>
74                 
75                 <listitem>
76                     
77                     <para>double、整数値のnnz行1列の行列,Aの行添字</para>
78                     
79                 </listitem>
80                 
81             </varlistentry>
82             
83             <varlistentry>
84                 
85                 <term>perm</term>
86                 
87                 <listitem>
88                     
89                     <para>double、整数値のn行1列の行列,最小次元規則配列</para>
90                     
91                 </listitem>
92                 
93             </varlistentry>
94             
95             <varlistentry>
96                 
97                 <term>invp</term>
98                 
99                 <listitem>
100                     
101                     <para>double、整数値のn行1列の行列,permの逆行列</para>
102                     
103                 </listitem>
104                 
105             </varlistentry>
106             
107             <varlistentry>
108                 
109                 <term>nofsub</term>
110                 
111                 <listitem>
112                     
113                     <para>
114                         
115                         double、整数値の1行1列の行列,圧縮記憶方式における非ゼロ要素の数の上限
116                         
117                     </para>
118                     
119                 </listitem>
120                 
121             </varlistentry>
122             
123         </variablelist>
124         
125     </refsection>
126     
127     <refsection>
128         
129         <title>説明</title>
130         
131         <para>
132             
133             コレスキー分解を適用する前に対称疎行列の行および列を交換する際に
134             
135             最小次元アルゴリズムが使用されます.
136             
137             このアルゴリズムはコレスキー分解の非ゼロ要素の数を減らします.
138             
139         </para>
140         
141         <para>
142             
143             n行n列の実対称疎行列<literal>A</literal>を指定すると,
144             
145             このコレスキー分解 <literal>U</literal> は,通常,
146             
147             <literal>A</literal>の上三角要素よりも非ゼロ要素が多くなる
148             
149             "塗りつぶし(fill in)"に苦しめられます.
150             
151             行列<literal>P'*A*P</literal>が同じく対称で,
152             
153             そのコレスキー分解の非ゼロ要素の数が最小となる
154             
155             交換行列 <literal>P</literal>を探します.
156             
157         </para>
158         
159     </refsection>
160     
161     <refsection>
162         
163         <title>例</title>
164         
165         <para>
166             
167             以下の例では,対称疎行列の順序付けを計算します.
168             
169             隣接構造体を計算する際に<literal>sp2adj</literal> を使用します.
170             
171         </para>
172         
173         <programlisting role="example"><![CDATA[ 
174 A = [
175 4. 1. 2. 0.5 2.
176 1. 0.5 0. 0. 0.
177 2. 0. 3. 0. 0.
178 0.5 0. 0. 5./8. 0.
179 2. 0. 0. 0. 16.
180 ];
181 A = sparse(A);
182 [xadj,iadj,val]=sp2adj(A);
183 n = size(A,"r");
184 [perm,invp,nofsub]=ordmmd(xadj,iadj,n)
185  ]]></programlisting>
186         
187         <para>
188             
189             以下の例では,対称疎行列の順序付けを計算します.
190             
191             <literal>invp</literal>が<literal>perm</literal>の
192             
193             逆行列であることを確認します.
194             
195         </para>
196         
197         <programlisting role="example"><![CDATA[ 
198     A = [
199     0.,  0.,  0.,  2.,  0.,  0.,  2.,  0.,  2.,  0.,  0. ;
200     0.,  0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0. ;
201     0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0. ;
202     2.,  0.,  0.,  0.,  0.,  0.,  2.,  0.,  2.,  0.,  0. ;
203     0.,  0.,  0.,  0. , 0.,  0.,  0.,  0.,  0.,  0.,  4. ;
204     0.,  0.,  0.,  0.,  0.,  0.,  0.,  3.,  0.,  3.,  0. ;
205     2.,  0.,  0.,  2.,  0.,  0.,  0.,  0.,  2.,  0.,  0. ;
206     0.,  0.,  0.,  0.,  0.,  3.,  0.,  0.,  0.,  3.,  0. ;
207     2.,  0.,  0.,  2.,  0.,  0.,  2.,  0.,  0.,  0.,  0. ;
208     0.,  0.,  0.,  0.,  0.,  3.,  0.,  3.,  0.,  0.,  0. ;
209     0.,  0.,  0.,  0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.];
210     n=size(A,1);
211     A=sparse(A);
212     [xadj,adjncy,anz]=sp2adj(A);
213     [perm,invp,nofsub]=ordmmd(xadj,adjncy,n);
214     perm(invp) 
215  ]]></programlisting>
216         
217         <para>
218             
219             以下の例では, 行列<literal>A</literal>と行列<literal>P'*A*P</literal>
220             
221             のコレスキー分解の疎パターンを計算します.
222             
223             "Computer Solution of Large Sparse Positive Definite Systems"のp.3 "Chapter 1: Introduction"を参照.
224             
225             コレスキー分解の非ゼロ要素の数は15,一方,行列<literal>P'*A*P</literal>のコレスキー分解は
226             
227             9個の非ゼロ要素を有することがわかります.
228             
229         </para>
230         
231         <programlisting role="example"><![CDATA[ 
232 A = [
233 4. 1. 2. 0.5 2.
234 1. 0.5 0. 0. 0.
235 2. 0. 3. 0. 0.
236 0.5 0. 0. 5./8. 0.
237 2. 0. 0. 0. 16.
238 ];
239 A = sparse(A);
240 // Aのコレスキー分解の疎パターンを調べる
241 U = sparse(chol(full(A)));
242 scf();
243 subplot(2,1,1);
244 PlotSparse(U,"x");
245 xtitle("Sparsity pattern of U, such that A=U''*U");
246 // 隣接構造体を取得
247 [xadj,iadj,val]=sp2adj(A);
248 // 複数の最小次元規則配列を計算
249 n = size(A,"r");
250 [perm,invp,nofsub]=ordmmd(xadj,iadj,n);
251 // 交換ベクトルを行列に変換
252 P=spzeros(n,n);
253 for i=1:n
254     P(perm(i),i)=1;
255 end
256 // P'*A*Pのコレスキー分解の疎パターンを調べる
257 U = sparse(chol(full(P'*A*P)));
258 subplot(2,1,2);
259 PlotSparse(U,"x");
260 xtitle("Sparsity pattern of U, such that P''*A*P=U''*U");
261  ]]></programlisting>
262         
263         <scilab:image localized="true">
264             
265             A = [
266             
267             4. 1. 2. 0.5 2.
268             
269             1. 0.5 0. 0. 0.
270             
271             2. 0. 3. 0. 0.
272             
273             0.5 0. 0. 0.625 0.
274             
275             2. 0. 0. 0. 16.
276             
277             ];
278             
279             A = sparse(A);
280             
281             U = sparse(chol(full(A)));
282             
283             scf();
284             
285             subplot(2,1,1);
286             
287             PlotSparse(U,"x");
288             
289             xtitle("Sparsity pattern of U, such that A=U''*U");
290             
291             [xadj,iadj,val]=sp2adj(A);
292             
293             n = size(A,"r");
294             
295             [perm,invp,nofsub]=ordmmd(xadj,iadj,n);
296             
297             P=spzeros(n,n);
298             
299             for i=1:n
300             
301             P(perm(i),i)=1;
302             
303             end
304             
305             U = sparse(chol(full(P'*A*P)));
306             
307             subplot(2,1,2);
308             
309             PlotSparse(U,"x");
310             
311             xtitle("Sparsity pattern of U, such that P''*A*P=U''*U");
312             
313         </scilab:image>
314         
315     </refsection>
316     
317     <refsection>
318         
319         <title>実装に関する注記</title>
320         
321         <para>
322             
323             この関数はMathematical Sciences Section, Oak Ridge National Laboratoryの
324             
325             Esmond G. Ng および Barry W. Peytonによる
326             
327             ソースコード "ordmmd.f",に基づいています.
328             
329             アルゴリズムはSPARSPAKライブラリのJoseph W.H. Liuによる genmmdルーチンに基づいています.
330             
331         </para>
332         
333     </refsection>
334     
335     <refsection>
336         
337         <title>参考文献</title>
338         
339         <para>
340             
341             "Minimum degree algorithm", Wikipedia contributors, Wikipedia, The Free Encyclopedia. http://en.wikipedia.org/wiki/Minimum_degree_algorithm
342             
343         </para>
344         
345         <para>
346             
347             "A new release of SPARSPAK: the Waterloo sparse matrix package", Alan George and Esmond Ng. 1984. SIGNUM Newsl. 19, 4 (October 1984), 9-13.
348             
349         </para>
350         
351         <para>
352             
353             "Computer Solution of Large Sparse Positive Definite Systems" by Alan George and Joseph Liu, Prentice-Hall, Inc. Englewood Cliffs, New Jersey, 1981
354             
355         </para>
356         
357         <para>
358             
359             "Implementation of Lipsol in Scilab", Rubio Scola, 1997, INRIA, No 0215
360             
361         </para>
362         
363     </refsection>
364     
365     <refsection role="see also">
366         
367         <title>参照</title>
368         
369         <simplelist type="inline">
370             
371             <member>
372                 
373                 <link linkend="sp2adj">sp2adj</link>
374                 
375             </member>
376             
377             <member>
378                 
379                 <link linkend="spchol">spchol</link>
380                 
381             </member>
382             
383         </simplelist>
384         
385     </refsection>
386     
387 </refentry>
388