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