WEKO3
アイテム
疎行列のフィルイン削減オーダリングにおける複雑な制約の定式化
https://doi.org/10.20729/00234837
https://doi.org/10.20729/002348374c1b37de-09eb-4acf-bc87-26ccdfab2479
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL6506011.pdf (1.3 MB)
2026年6月15日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, 論文誌:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Journal(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-06-15 | |||||||||
| タイトル | ||||||||||
| タイトル | 疎行列のフィルイン削減オーダリングにおける複雑な制約の定式化 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Formulation of Complex Constraints in Fill-in Reduction Ordering for Sparse Matrices | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [一般論文（特選論文）] 量子アニーリング，疎行列，フィルイン削減，オーダリング | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| ID登録 | ||||||||||
| ID登録 | 10.20729/00234837 | |||||||||
| ID登録タイプ | JaLC | |||||||||
| 著者所属 | ||||||||||
| 山梨大学 | ||||||||||
| 著者所属 | ||||||||||
| 山梨大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| University of Yamanahi | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| University of Yamanahi | ||||||||||
| 著者名 |
小見山, 朋子
× 小見山, 朋子
× 鈴木, 智博
|
|||||||||
| 著者名(英) |
Tomoko, Komiyama
× Tomoko, Komiyama
× Tomohiro, Suzuki
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 科学技術計算において，疎行列を含む連立一次方程式の求解は頻繁に登場する．そのような方程式を直接解法で解くと，疎行列の零要素が非零になるフィルインが頻繁に発生し，メモリや計算のコストが増加することがある．この問題に対して，フィルイン数の発生を抑えるように行列の要素を並べ替えるオーダリングという手法が利用されてきた．特に，フィルイン数が最小になるオーダリングを求める問題はNP完全問題であり，多段決定問題として発見的手法により計算されてきた．本論文では，フィルイン数削減のためのオーダリングを求める問題を静的な0-1整数計画問題として定式化し，これを量子アニーリングで解くという新たなアプローチを提案する．さらに，この問題の複雑な制約を定式化するために必要になる補助変数を削減するいくつかの工夫を評価する．疑似量子アニーリングマシンによる実験により，小さいサイズの行列に対して従来手法よりもフィルイン数が少ないオーダリングが得られる可能性を示す． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Solving sparse matrix linear systems appears frequently in scientific and engineering computations. Solving such equations with a direct solver frequently results in fill-ins in which the zero elements of the sparse matrix become nonzero. It increases memory and computation costs. To overcome this issue, a method called “ordering” has been used, in which the matrix elements are rearranged to minimize the number of fill-ins. The problem of finding an ordering that minimizes the number of fill-ins is NP-complete and has been computed using dynamic heuristics algorithms. In this paper, we formulate the problem to find the ordering with the minimum fill-ins as a static combinatorial optimization problem and solve it with quantum annealing. In addition, several techniques are presented to reduce the number of auxiliary variables that arise when formulating the complex constraints of this problem. Experiments show that the orderings obtained by the quantum-inspired annealer sometimes achieve fewer fill-ins than those obtained by the conventional method. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00116647 | |||||||||
| 書誌情報 |
情報処理学会論文誌 巻 65, 号 6, p. 1082-1090, 発行日 2024-06-15 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7764 | |||||||||
| 公開者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
