改訂シンプレックス法におけるLU分解の高速化手法

カテゴリ: 全国大会

論文No: 3-100

グループ名: 【全国大会】平成16年電気学会全国大会論文集

発行日: 2004/03/17

タイトル(英語): The Speed-up Scheme of LU Decomposition in the Revised Simplex Method

著者名: 吉田 直樹(千葉工業大学),前川 仁孝(千葉工業大学),伊與田 光宏(千葉工業大学)

著者名(英語): Naoki Yoshida(Chiba Institute of Technology),Yoshitaka Maekawa(Chiba Institute of Technology),Mitsuhiro Iyoda(Chiba Institute of Technology)

キーワード: 改訂シンプレックス法|LU分解法|並列処理

要約(日本語): 線形計画問題(LP問題)は,ある線形不等式を制約条件として目的関数と呼ばれる線形関数を最大化または最小化する問題であり,生産計画問題,輸送計画問題など産業面の幅広い分野に用いられている.LP問題の解法は,中規模では主にLU分解法を用いた改訂シンプレックス法が用いられている.本稿では,この解法の中で最も時間のかかるLU分解における処理量の削減を行い,並列処理により高速化した.共有メモリ型並列計算機上による実装と評価を行った結果,LU分解の処理量を削減することで約2倍高速化されることが確かめられた.また,処理量の削減と合わせて効率良く並列処理することで最大14.65倍高速化されることが確認できた.

原稿種別: 日本語

PDFファイルサイズ: 1,796 Kバイト