行置換によるスパース行列の効率的縮小アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
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条件をそのまま使用できるので, 行列縮小化の条件をつねに一つに統一できる特徴がある.
- 一般社団法人情報処理学会の論文
- 1985-03-15
著者
関連論文
- 複合語の分野連想語の効率的決定法
- 日本語定型表現のパターン記述規則と効率的な照合アルゴリズム
- 意味変化率を考慮した文書短縮方法
- 日本語定型表現の分析と効率的照合アルゴリズム
- 活用語を含む助詞的定型表現の分析
- ダブル配列におけるキー削除の効率化手法
- 探索木法とその応用 ( キー検索技法 3)
- 大規模文書データに対する用例文の効率的検索アルゴリズム
- 薄膜磁性線三値記憶装置
- 接頭辞ダブル配列における空間効率を低下させないキー削除法(情報検索)
- ダブル配列におけるキー削除の効率化手法
- ダブル配列における動的更新の効率化アルゴリズム
- パターンマッチングマシンの効率的記憶検索法
- 多属性項目の履歴情報に基づく電子メイル文書のフィルタリング手法
- 多属性項目の履歴情報に基づく電子メイル文書のフィルタリング手法
- 履歴情報を考慮したメイル文書のフィルタリング手法
- バースト誤り訂正2元巡回符号の符号点分布
- A-6-13 バースト誤り訂正2進巡回AN符号の符号点分布
- 高能力2進巡回AN符号を構成するための符号語数の考察
- 2^m-1個の符号語をもつバースト誤り訂正2進巡回AN符号
- 2進巡回AN符号の記号交錯による確率的なバースト誤り訂正
- 自己相補的な2進巡回AN符号とその最小距離
- 自然数の積A_1・pで生成されるバースト誤り訂正2^k進巡回AN符号
- バースト誤り訂正のための2K進巡回AN符号
- バースト誤り訂正可能な繰り返し2進巡回AN符号
- 2^k 進巡回 AN がバースト誤り訂正能力をもつための必要条件について
- バースト誤り訂正のための2進巡回AN符号と2^K進巡回AN符号
- A-183 バースト誤り訂正のための2進巡回AN符号と2^k進巡回AN符号(A-7. 情報理論,一般講演)
- バ-スト誤り訂正奇数進巡回AN符号
- 行置換によるスパース行列の効率的縮小アルゴリズム
- 局所的にスタックを使用するLALR(1)パ-サの拡張
- 多数決論理復号可能な巡回ST-AN符号
- 対称3進巡回AN符号 (多値論理およびその応用)
- 巡回ST-AN符号について
- 有限状態機械の効率的記憶検索法
- 分野連想語を用いたパッセージ特定手法
- RD-002 重複レコードの多い大規模トライ辞書の圧縮(データベース,査読付き論文)
- 転置ファイルによる大規模 n-gram データの検索システム
- 転置ファイルによる大規模 n-gram データの検索システム
- パトリシアトライに対する簡潔な配列表現
- LD_008 ダブル配列におけるキャッシュの効率化(D分野:データベース)
- 2次記憶上のダブル配列の効率的検索法
- キーワードの遅延抽出を考慮した文書検索構造の効率的構成法
- トライ構造を用いた共起情報の効率的検索アルゴリズム
- 特徴ベクトルによる全文検索の一改善法
- 拡張ハッシュ法における部分文字列検索の設計と実現
- トライ構造を用いた共起情報の効率的検索アルゴリズム
- グラフ構造に対する効率的記憶検索法
- 文書レイアウトにおける自動図表配置手法
- 特徴ベクトルを用いた全文検索における高速化手法
- ストリングパターンマッチングマシンの文字列置換への拡張法
- ストリングパターンマッチングマシンの動的構成法
- 片仮名異表記の生成および統一手法
- ストリングパターンマッチングマシンにおける検索キー追加方法
- LRパーサを用いた文字列置換アルゴリズム
- 形態素置換による文書短縮法
- 階層化による2進ディジタル探索(BDS)木の改善
- 拡張ハッシュ法による検索技法の拡張 : 部分文字列検索と順検索への拡張
- 時間推移を考慮した単語の重要度決定手法
- 格構造解析における概念階層の効率的判定アルゴリズム
- キーワード抽出を用いた文書自動分類手法
- パトリシアトライ構造の効率的な圧縮アルゴリズム
- 三進算術演算装置
- 電子計算機による多重3値論理関数の簡単化
- 準安定状態をもつ順序論理回路とその論理解析
- 準安定状態をもつ順序回路の合成
- 3個のNAND/NOR回路を基本回路とする3相マルチバイブレ-タ
- 三相マルチバイブレータ(その2)
- 三相マルチバイブレーター(その1)
- トランジスタ双安定MVのトリガに関する研究 その2 転位コンデンサのあるセット・リセット形の場合
- 知識表現モデルMERMにおける定量化の一表現法
- 2進木トライ構造の効率的な圧縮手法
- トライ構造による概念階層の高速判定アルゴリズム
- 階層化概念辞書の高速検索アルゴリズム
- 連載講座「キー検索技法」の編集にあたって
- 大学で育成すべき自然言語処理技術者とは?
- 画像,音声,テキストに対するマルチデータ処理技術の統合化とその応用
- HTML形式の表構造に対する一索引化手法
- WWW空間上に存在する表構造の一索引化手法
- キーワード構成の分析とその応用
- 接続情報を加味した形態素辞書による形態素解析の高速化
- LR(1)構文解析表の動的構成法
- 日本語時間表現の一解釈法
- 日本語文における時間表現の形式化手法
- 携帯電話情報サービスのための新聞記事要約の研究
- 新製品ニュース管理システムのための文と段落のタイプ抽出方法
- 4V-6 技術解説記事データベースのためのXML文書作成ツールの開発
- テキストベースの一提案
- 画像,音声,テキストに対するマルチデータ処理技術の統合化とその応用
- 自然言語インタフェースにおける間接発話文の意図理解法
- 類似用例文の効率的検索手法とその応用
- 二つのトライを用いた辞書検索アルゴリズム
- トライ構造における共通接尾辞の圧縮アルゴリズム
- 自然言語インタフェースにおける間接発話文の意図理解法
- 自然言語入力に対する知的コマンドインターフェイスICIにおける入力文の意図理解
- パージングテーブルによる弱順位パーザの構成法
- 文字列照合マシンを利用した複合語キーワードの効率的抽出法
- パージングテーブルによる弱順位パーザの補足
- 文脈自由言語に対する構文解析部の自動生成
- BCH符号によるミニコンピュータ結合システムの誤り制御