行置換によるスパース行列の効率的縮小アルゴリズム

• Item type: Journal(1)
• 公開日: 1985-03-15
• タイトル: 行置換によるスパース行列の効率的縮小アルゴリズム
• タイトル / 言語: en
• タイトル: An Effcient Algorithm of Reducing Sparse Matrices by Row Displacements
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 徳島大学工学部情報工学科
• 著者所属: 徳島大学工学部情報工学科
• 著者所属: 徳島大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, The University of Tokushima
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, The University of Tokushima
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, The University of Tokushima
• 著者名: 青江, 順一; 山本, 米雄; 島田, 良作
• 著者名(英): Junichi, Aoe; Yoneo, Yamamoto; Ryosaku, Shimada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Tarjanらは スバース行列の縮小法として行置超換による方法(ffd 法と呼ぶ)を採用し 次を満足するための条件(HD条件と呼ぶ)とその理論的評価を与えた.(1)行列のすべての非零要素数をn 行の大きさをmとするとき 記憶量をn+2m語とする.(2)最悪の場合の探索時間をΟ(1)とする.本論文では 種々のスパース行列に対する実験結果に基づいてffd法とHD条件を評価し ffd法の改善法とHD条件に代る経験的な条件を提案する.まず ffd法の行置換法と行ソート法が改善され 改善された縮小法をffds 法と呼ぶ.次に このffds法が上記の(1)と(2)を満足するための条件(AV条件と呼ぶ)を提案する.このAV条件は経験的なものであるが HD条件より判定が能率的に行え しかも適用できるスパース行列の範囲がHD条件より大幅に広くなる.最後に AV条件を満足しない行列に対する縮小法の拡張を考える.Tarjanらの拡張法では HD条件以外にED条件と呼ばれるもう一つの条件を必要とする.しかし 本論文による拡張法ではAV条件をそのまま使用できるので 行列縮小化の条件をつねに一つに統一できる特徴がある.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 26, 号 2, p. 211-218, 発行日 1985-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764