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

情報処理学会

書誌事項

タイトル別名
  • An Effcient Algorithm of Reducing Sparse Matrices by Row Displacements

この論文をさがす

抄録

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条件をそのまま使用できるので 行列縮小化の条件をつねに一つに統一できる特徴がある.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1050282812867009024
  • NII論文ID
    110002724001
  • NII書誌ID
    AN00116647
  • ISSN
    18827764
  • Web Site
    http://id.nii.ac.jp/1001/00015818/
  • 本文言語コード
    ja
  • 資料種別
    journal article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ