結論 - .PSfrag replacements - 第7回環瀬戸内応用数理研究部会シンポジウム2003

.PSfrag replacements

6. 結論

これは，JSORω法の境界の最適加速係数よりも大きい．新しいデータを多く用いることにより，境界の計算に，より大きな加速係数を用いることができたと考えられる．また

200 × 200，500 × 500

の場合では，

ω，ω 1

，ω

2

がほとんど同じ値であるが，1000

× 1000

の場合には

ω

と

ω 1

，ω

2

での違いが生じる．これについては今後の課題とし，他の問題や格子点数の異なる計算を行うことで，違いが生じる要因を特定していきたい．

表

2:

最適加速係数

配列数

ω ω 1 ω 2

収束回数

200 × 200(JSOR ω

法)

1.981 1.81 1.79 1508 500 × 500(JSORω

法)

1.992 1.84 1.83 3713 1000 × 1000(JSOR ω

法)

1.996 1.85 1.85 7356 200 × 200(PSOR ω

法)

1.970 1.97 1.98 842 500 × 500(PSORω

法)

1.988 1.97 1.98 2120 1000 × 1000(PSORω

法)

1.994 1.95 1.94 4274

5. ３次元計算の場合の計算結果

並列計算が十分その威力を発揮できると思われる大規模計算について，以下のような領域

Ω = {(x, y, z)|0 <

x < 1, 0 < y < 1, 0 < z < 1}

における三次元のポアソン方程式の境界値問題

 



∂ ² u

∂x ² + ∂ ² u

∂y ² + ∂ ² u

∂z ² = −2 (x, y, z) ∈ Ω u(x, y, z) = 0 (x, y, z) ∈ ∂Ω

(8)

について同様の計算を行った．計算格子数は

200 ×200 ×200

であり，初期条件はすべての格子点で

u i,j,k = 0

とした．それぞれの方法で得られた結果について，最適の収束回数を表

3

に示す．JSORω法については，

２次元の場合の結果から，ω

= 1 . 980，ω 1 = 1 . 81，ω 2 = 1 . 81

として計算を行い，PSOR

ω

法については，

ω = 1.970，ω 1 = 1.98，ω 2 = 1.98

とした．

表

3:

三次元での計算結果

SOR

法

JSOR

法

JSORω

法

PSOR

法

PSORω

法

425 606 576 424 418

この表から，三次元計算で，収束判定法を変えた場合にも，SOR法と

PSOR

法がほぼ同じ収束をすることがわかる．またそれに比べ，JSOR法は収束回数が多い．また，JSORω法と

JSOR

法と比較すると，タスク境界での加速係数を小さく取ることにより，収束性が改善していることがわかる．さらに，PSORω法と

PSOR

法との比較から，タスク境界での加速係数を変えることで，収束性に多少の改善がみられた．以上のように，三次元計算の場合にも２次元の場合で得られたのと同様の結果が得られた．

束性に与える影響を具体的に考察することによって，データ受け渡し部分に着目し，数値スキームの変更で並列計算が十分な威力を発揮することができるかどうかについて考察した．JSOR法では，データ受け渡し部分の計算で古いデータを過大評価してしまうことで収束性を下げていると考えられるので，JSOR 法の加速係数を部分的に変更する

JSORω

法を提案し，数値計算を行った．その結果，タスク境界の加速係数を低く取ることで，JSOR法の収束性を改善することが可能となった．さらに，JSOR法の手順を変更した

PSOR

法について数値計算を行い，SOR法と

PSOR

法の収束性が同じであることを裏付けた．また，タスク境界の加速係数を変化させることで，多少ではあるが収束性を改善できることがわかった．最後に，より大規模計算である三次元問題の数値計算を行った．その結果，２次元の場合と同様のことが示され，本研究で提案した考え方は，一般的な数値計算においても適用できるものと思われる．以上のことから，領域を分割して数値計算を行う場合，信頼性の高い新しいデータを用いること，タスク境界の加速係数を部分的に変化させることが，収束性に大きな影響を与えることがわかった．今回は収束性だけを見たため，性能評価までは行っていない．今後は，実際にネットワークを介した数値計算，データの転送方法，通信路の性能等も含めた評価を行う予定である．

参考文献

1) D. Xie, New Parallel Iteration Methods, New Nonlinear Multigrid Analysis, and Application in Computational Chemistry, Ph.D. Thesis, UH/MD Research report 208, University of Houston, Houston, TX(1995).

2) D. Xie, L. Adams, New Parallel SOR Method by Domain Partitioning, SIAM J . Sci. Comput. 20,

No. 6, pp.2261-2281(1999)．

１次元カオス写像を用いたモンテカルロ積分

矢野忠（愛媛大学工学部）, 和田武（愛媛大学総合情報処理センター）, 矢野浩一（統計数理研究所）, 江沢康生（愛媛大学理学部）

１はじめに

一次元のカオス写像（以下ロジスティック写像という） x _n ₊ ₁ = ax _n (1 − x _n ) ^は ^であれば、カオス的な振舞をすることはよく知られている[1]。この一次元写像を擬似乱数として使えないかということは誰でも一度は考えてみることであろう[2][3]。擬似乱数として使えるためには乱数の一様性が必要であるが、これは満たされていないことがわかっている[4]。また、

乱数の発生の効率といった点でもどうもあまりよくないようである。

3.57 a > ⋅⋅⋅

そういうことを知った上でもロジスティック写像をやはり使えるところはないかとかその性質の幾分かを調べておくのは意味があるだろうと考える。

ここではモンテカルロ積分にどのように使うかということについての予備的な試行について報告したい。

２モンテカルロ積分

多次元の数値積分を行うときには多分モンテカルロ積分がほぼ唯一の積分評価手段となるであろう。物理学ではいろいろのところで多重積分が現れてくる。たとえば、分子軌道法ではいろいろな行列要素に積分が現れてくるし、宇宙線によるパイオンの多重発生等ではその位相空間の積分とかが必要である。

そのような例として量子化学の分子軌道法に現れる積分[5]を取り上げてみよう。

² ² ² ^cr 1 ,

k ∫∫∫ V z e ⁻ dxdydz = ^k ² ⁼ ^c _π ⁵ ^, ^c ⁼ ^1.59 （１）

である。3 重積分の値が 1/ であり、は規格化因子である。これについて普通の一様擬似乱数を用いて評価すれば、 10 ^{回の試行で相対誤差が} 1.7% [6]が得られるが、ロジスティック写像

k 2 n )

k

4 1 4 (1

n n

x ₊ = x − x を用いて評価すれば、その値は 67.3%となり、とても実用になるようなものではない。これはなんの修正手段も施さずにロジスティック写像を用いたためであり、

乱数としての一様性がないので、その値が悪いのは仕方がないとしても、では一様であるところのみを用いればいい結果が果たして得られるのだろうか。

それについての数値実験の結果はまだ出ていないのでなんともいえないが、多分答は肯定的なのであろう。予備的な数値実験ではなかなか肯定的な結果が得られていないが。

上の推論が正しいかどうかを式（１）のような 3 重積分ではなく、１重積分で

2 1 2

0 1 0.3413447

2 x

e dx π

− =

∫ ^⋅⋅⋅ （２）

で試してみた。数値実験したケースは以下の 3 通りである。

(1) ロジスティック写像をそのまま使用する

(2) ロジスティック写像から一様な分布の 0.2〜0.8 の範囲を使用する (3) メルセンヌツイスター擬似乱数[7]を使用する（比較用）

３結果

試行結果をグラフで示す。今回のモンテカルロの試行は 5 万回行い、そのうち 50 個所を取り出してグラフ化した。

以下にそれぞれの結果のグラフ（ファイル名）を示す。

(1) ロジスティック写像をそのまま使用した場合 LogisticChaos.jpg

図１ロジスティック写像

(2) ほぼ一様な 0.2〜0.8 の範囲を使用した場合 Logistic0.2to0.8.jpg

図２ロジスティック写像（0.2〜0.8）

(3) メルセンヌツイスター擬似乱数を使用する Mersenne.jpg

図３

メルセンヌツイスター擬似乱数

４議論とまとめ

試行回数はまだ十分ではないが、図１〜図３に示したよう順に収束の程度がよくなっていることがわかる。メルセンヌツイスター擬似乱数の場合の収束がよいのは一様性が 3 つの場合の中で一番よいからであり、図１の一番収束が悪いのは一様性がないからであろう。図 2 がその中間にあるのは一様性がその図 1 に比べてかなり改善されたためであろう。これらの予備的な数値実験を参考にしながら、多重積分の場合を調べていくつもりである。

参考文献

[1] たとえば、H. G. Schuster, Determinisitic Chaos, (VCH 1988).

[2] 日野英司、カオスと乱数（愛媛大学工学部卒業論文 1990）.

[3] 香田徹、柿本厚志、擬似乱数とカオス、情報処理学会論文誌 27(1986), 289-296.

[4] 梅野健、カオスと計算、数理科学 415(1998) 60-68 または[2]

[5] 藤永茂著、「分子軌道法」（岩波書店、1980） 295-300.

[6] 合田英輔、岩田将洋、一次元カオス写像を用いたモンテカルロ積分（愛媛大学工学部卒業論文 2003）.

[7] http://www.math.keio.ac.jp/˜matumoto/mt.html Mersenne-Twister は 2^(19937) の長い周期を持つモンテカルロ用擬似乱数である。

CG 画像の特徴を考慮した可逆画像圧縮法について

* 井上啓、 ** 黒塚豊、 * 古市茂

* 山口東京理科大学、 ** アルファシステムズ

1 ^はじめに

コンピュータグラフィックス

(CG)

画像には「

(1)

同一色や均一なグラデーションといった色に偏りの大きい領域

(2)

濃淡に大きな違いがある画素同士が隣り合う色に偏りの小さい領域」が含まれている。

Windows

の標準画像フォーマット形式であるビットマップ形式

(BMP)

において、これらの領域の特徴を画素

(

ピクセル

)

単位でみてみると、それぞれ、「

(1)

隣り合う画素同士の差分を取ると同じ数字が複数個続けて並ぶ。

(2)

色の境目が含まれているため、ある一定方向の近隣の画素以外は画素値同士のの関連性が低い。」といった傾向として現れてくる。したがって、

(1)

の色の偏りの大きい領域においては、隣り合う画素同士の差分を取ってから

(

差分符号化

[1])

、ある値がいくつ並んでいるという形で記述するランレングス符号化を行うと画像圧縮効果が高いと考えられる

[4]

。また、

(2)

の色の偏りの少ない領域においては、実際の画素値を近隣の画素の線形結合で近似する画像符号化である予測符号化

([3, 5])

が圧縮効果が高いものと考えられる。予測符号化を行った後、予測誤差が少ないほど予測誤差の分布が

0

付近に値を多く取る偏りを持った分布を生成するため、ハフマン符号化

[2]

などエントロピー符号化の前処理として予測符号化を用いることで、エントロピー符号化による圧縮の効果

(

偏りのある分布の方が圧縮率が良い

)

を高めることができる。

本発表では、ビットマップ形式で保存された

CG

画像を対象として、いくつかのブロックに領域分割し、各領域の画像の性質に応じて、適応的に上記の

2

つの圧縮法を切り替えることで

CG

画像に適した可逆画像圧縮法について考察する。

2 色の偏りの大きい領域に対する画像符号化

2.1 差分符号化

色の偏りの大きい領域は、同じ画素値が連続して現れたり、画素値が一定間隔で増加

(

または、減少

)

していくといった傾向がある

(

図

2.1)

。

119 119 119 119 120

117 118 119 120 121

122 122 122 122 122

119 119 119 119 120

117 118 119 120 121

122 122 122 122 122

このような領域において、現在の位置の画素値から一つ前の位置の画素値を引き、実際の画素値とその差分値を置き換える操作を差分符号化という

[1]

。ここでは、最初に横方向に関して差分符号化を行い

(

図

2.2)

、次に、一番左側の列のデータに対して、縦方向に関して差分符号化を行う

(

図

2.3)

。

0 0 0 -1 120

-1 -1 -1 -1 121

0 0 0 0 122

0 0 0 -1 120

-1 -1 -1 -1 121

0 0 0 0 122

0 0 0 -1 -1

-1 -1 -1 -1 -1

0 0 0 0 122

0 0 0 -1 -1

-1 -1 -1 -1 -1

0 0 0 0 122

2.2 ランレングス符号化

ランレングス符号化は、ある記号がいくつ続いているかで元の記号列を置き換える符号化である。たとえば、

aaaaaaaaabbbbbccccdddddd

という記号列は

1

番目に

a

^{が個続き、}

2

番目に

b

^が

5

個続き、

3

番目に

c

^が

4

個続き、

最後に

d

^が

6

個続いている。したがって、この記号列をランレングス符号化すると

a 9 b 5 c 4 d 6

となる。ここで、

2.1

節で説明した差分符号化された画像データに対してランレングス符号化を適用する。画素の走査では、行の一番最後の画素に達したら、次の行の先頭の画素に移動させる

(

図

2.4)

。

図

2.3

の差分符号化された画像データにランレングス符号化を適用すると、図

2.5

のようになる。

3 0

7 -1 4

0 122

3 0

7 -1 4

0 122

これらの

2

つの画像符号化を行った後には、

15

バイト

(1

文字あたり

1

バイト

)

あった画像データ量が

7

バイトに圧縮されている。

2.3 ハフマン符号化

ハフマン符号は、記号列の各記号の出現頻度の高い符号にできるだけ符号長の短い符号を割り振ることで、記号列の平均符号量を最小にする符号化である

[2]

。たとえば、

adabaeadaacaabbf bbcddddef f

という記号列おいて、各記号の出現頻度は以下の通りである。

a b c d e f

8 5 2 6 2 3

このとき、出現頻度の低い記号同士を結び付けて新たな記号として登録していき、木を作成する。この木に対して、左側の枝に

0

、右側の枝に

1

を割り当てるとハフマン木が完成する

(

図

2.6)

。

e c

(2) (2)

(4)

f (3) (7)

b (5)

d (6) (11)

a (8)

(15)

(26) 0

0 0 0

0

1 1 1

1

ドキュメント内第7回環瀬戸内応用数理研究部会シンポジウム2003 (ページ 38-47)

結論

.PSfrag replacements

6. 結論

200 × 200，500 × 500

ω，ω 1

2

× 1000

ω

ω 1

2

2:

ω ω 1 ω 2

200 × 200(JSOR ω

1.981 1.81 1.79 1508 500 × 500(JSORω

1.992 1.84 1.83 3713 1000 × 1000(JSOR ω

1.996 1.85 1.85 7356 200 × 200(PSOR ω

1.970 1.97 1.98 842 500 × 500(PSORω

1.988 1.97 1.98 2120 1000 × 1000(PSORω

1.994 1.95 1.94 4274

5. ３次元計算の場合の計算結果

Ω = {(x, y, z)|0 <

x < 1, 0 < y < 1, 0 < z < 1}

 



∂ 2 u

∂x 2 + ∂ 2 u

∂y 2 + ∂ 2 u

∂z 2 = −2 (x, y, z) ∈ Ω u(x, y, z) = 0 (x, y, z) ∈ ∂Ω

(8)

200 ×200 ×200

u i,j,k = 0

3

= 1 . 980，ω 1 = 1 . 81，ω 2 = 1 . 81

ω

ω = 1.970，ω 1 = 1.98，ω 2 = 1.98

3:

SOR

JSOR

JSORω

PSOR

PSORω

425 606 576 424 418

PSOR

JSOR

PSOR

JSORω

PSOR

PSOR

参考文献

1) D. Xie, New Parallel Iteration Methods, New Nonlinear Multigrid Analysis, and Application in Computational Chemistry, Ph.D. Thesis, UH/MD Research report 208, University of Houston, Houston, TX(1995).

2) D. Xie, L. Adams, New Parallel SOR Method by Domain Partitioning, SIAM J . Sci. Comput. 20,

No. 6, pp.2261-2281(1999)．

１次元カオス写像を用いたモンテカルロ積分

矢野 忠（愛媛大学工学部）, 和田武（愛媛大学総合情報処理センター）, 矢野浩一（統計数理研究所）, 江沢康生（愛媛大学理学部）

１ はじめに

乱数の発生の効率といった点でもどうもあまりよくないようである。

3.57 a > ⋅⋅⋅

そういうことを知った上でもロジスティック写像をやはり使えるところはないかとかその性質の 幾分かを調べておくのは意味があるだろうと考える。

ここではモンテカルロ積分にどのように使うかということについての予備的な試行について 報告したい。

２ モンテカルロ積分

そのような例として量子化学の分子軌道法に現れる積分[5]を取り上げてみよう。

2 2 2 cr 1 ,

k ∫∫∫ V z e − dxdydz = k 2 = c π 5 , c = 1.59 （１）

である。3 重積分の値が 1/ であり、 は規格化因子である。これについて普通の一様擬似 乱数を用いて評価すれば、 10 回の試行で相対誤差が 1.7% [6]が得られるが、ロジスティッ ク写像

k 2 n )

k

4

1 4 (1

n n

x + = x − x を用いて評価すれば、その値は 67.3%となり、とても実用になるよう なものではない。これはなんの修正手段も施さずにロジスティック写像を用いたためであり、

乱数としての一様性がないので、その値が悪いのは仕方がないとしても、では一様であるとこ ろのみを用いればいい結果が果たして得られるのだろうか。

それについての数値実験の結果はまだ出ていないのでなんともいえないが、多分答は肯 定的なのであろう。予備的な数値実験ではなかなか肯定的な結果が得られていないが。

上の推論が正しいかどうかを式（１）のような 3 重積分ではなく、１重積分 で

2

1 2

0

1 0.3413447

2

x

e dx π

∂ ² u

∂x ² + ∂ ² u

∂y ² + ∂ ² u

∂z ² = −2 (x, y, z) ∈ Ω u(x, y, z) = 0 (x, y, z) ∈ ∂Ω

矢野忠（愛媛大学工学部）, 和田武（愛媛大学総合情報処理センター）, 矢野浩一（統計数理研究所）, 江沢康生（愛媛大学理学部）

１はじめに

そういうことを知った上でもロジスティック写像をやはり使えるところはないかとかその性質の幾分かを調べておくのは意味があるだろうと考える。

ここではモンテカルロ積分にどのように使うかということについての予備的な試行について報告したい。

２モンテカルロ積分

² ² ² ^cr 1 ,

k ∫∫∫ V z e ⁻ dxdydz = ^k ² ⁼ ^c _π ⁵ ^, ^c ⁼ ^1.59 （１）

である。3 重積分の値が 1/ であり、は規格化因子である。これについて普通の一様擬似乱数を用いて評価すれば、 10 ^{回の試行で相対誤差が} 1.7% [6]が得られるが、ロジスティック写像

x ₊ = x − x を用いて評価すれば、その値は 67.3%となり、とても実用になるようなものではない。これはなんの修正手段も施さずにロジスティック写像を用いたためであり、

乱数としての一様性がないので、その値が悪いのは仕方がないとしても、では一様であるところのみを用いればいい結果が果たして得られるのだろうか。

それについての数値実験の結果はまだ出ていないのでなんともいえないが、多分答は肯定的なのであろう。予備的な数値実験ではなかなか肯定的な結果が得られていないが。

上の推論が正しいかどうかを式（１）のような 3 重積分ではなく、１重積分で

∫ ^⋅⋅⋅ （２）

３結果

試行結果をグラフで示す。今回のモンテカルロの試行は 5 万回行い、そのうち 50 個所を取り出してグラフ化した。

４議論とまとめ

[3] 香田徹、柿本厚志、擬似乱数とカオス、情報処理学会論文誌 27(1986), 289-296.

[5] 藤永茂著、「分子軌道法」（岩波書店、1980） 295-300.

[6] 合田英輔、岩田将洋、一次元カオス写像を用いたモンテカルロ積分（愛媛大学工学部卒業論文 2003）.

* 井上啓、 ** 黒塚豊、 * 古市茂

1 ^はじめに