WEKO3
アイテム
彩色数を最小化するMulti-coloring法のQUBO定式化
https://ipsj.ixsq.nii.ac.jp/records/241673
https://ipsj.ixsq.nii.ac.jp/records/241673ba3ece58-8981-4e47-ab98-f379830107c4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-ARC24259008.pdf (968.4 kB)
2026年12月9日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, ARC:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-12-09 | |||||||
| タイトル | ||||||||
| タイトル | 彩色数を最小化するMulti-coloring法のQUBO定式化 | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 最適化 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 山梨大学 | ||||||||
| 著者名 |
鈴木, 智博
× 鈴木, 智博
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 疎行列連立一次方程式の反復解法では，少ない反復回数で解を得るための収束性と，並列コンピュータの性能を発揮するための並列性が要求される．近年の高い並列性を持つハードウェアの性能を引き出すために，反復解法の並列性は重要な要素となっている．行列要素間の依存性を減らすことで並列性を高めることが可能であり，この目的のためのオーダリングを並列オーダリングと呼ぶ．並列オーダリングの代表的な手法である Multi-coloring 法は，なんらかの規則で各頂点の彩色を行い，同色の頂点が輪番となるようオーダリングを行う．同色に分類された頂点に対応する行列要素は同時に処理することができるため，彩色数は少ないほど並列性が高くなる．疎行列を隣接グラフとして表現し，グラフ彩色問題を解くことで各頂点の彩色を行うことが可能である．しかし，彩色数を最小にするグラフ彩色問題は NP 困難な問題であるため，ヒューリスティックスによる解法が用いられることが多い．本発表では，グラフ彩色問題を QUBO 定式化し，QA マシンで解き，得られた彩色によるオーダリングを反復法の前処理として適用した際の効果を従来法と比較して評価する．更に，彩色数の反復削減手法を導入し，彩色数の削減効果を検証する． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10096105 | |||||||
| 書誌情報 |
研究報告システム・アーキテクチャ（ARC） 巻 2024-ARC-259, 号 8, p. 1-6, 発行日 2024-12-09 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 2188-8574 | |||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
