【研究分野】数理情報学

【研究領域課題番号】17K00028 (KAKENデータベースで見る）

【研究キーワード】

組合せ最適化 / アルゴリズム / ストリーミングアルゴリズム / 劣モジュラ関数 / マトロイド / マッチング / 近似アルゴリズム / コミュニティ検出 / ストリーミング計算 / 数理工学 / 情報基礎 / 数理モデル

【研究成果の概要】

本年度は，昨年度に引き続き，大規模なネットワークを解析するための基本的な問題のひとつである，制約付き劣モジュラ関数最大化問題を扱い，この問題に対するストリーミングアルゴリズムの計算複雑度の解析に取り組んだ．昨年度に，制約付き劣モジュラ関数最大化問題に対する近似不可能性と空間複雑度との関係の解明に取り組み，入力データがストリームとして与えられメモリが制限されている状況において，0.585近似よりよい近似比を達成するアルゴリズムが存在しないことを示した．この成果は，本年度に論文改訂を経て査読付き論文誌SIAM Journal on Discrete Mathematicsに採択された．また，組合せ最適化における基本的な概念であるマトロイドに関連して，買い手が動的に市場にやってくる組合せ市場での価格付け問題に取り組み，昨年度に得た成果を改善したものが査読付き論文誌SIAM Journal on Discrete Mathematicsに掲載された．さらに，二部マッチングマーケットにおいて，エージェントが確率過程にもとづき出入りする場合に，貪欲アルゴリズムなど基本的なアルゴリズムの漸近的性能と各エージェントの待ち時間との関係を解明した．この成果は，ウェブとインターネット経済に関する査読付き国際会議The 17th Conference on Web and Internet Economics(WINE)に採択された．

【研究種目】基盤研究(C)

【研究期間】2017-04-01 - 2023-03-31

【配分額】4,420千円 (直接経費: 3,400千円、間接経費: 1,020千円)

【研究分野】高性能計算

【研究領域課題番号】15H02709 (KAKENデータベースで見る）

【研究キーワード】

高性能計算 / 非同期 / 省通信・省同期 / メニイコア / 自動チューニング / 分割統治法 / 時空間タイリング / 時間方向並列 / 非同期アルゴリズム / 通信回避 / 超メニイコア / スレッド数自動調整 / ハイパフォーマンス・コンピューティング / アルゴリズム / 数理工学 / 通信回避や非同期性 / ハイパフォーマンスコンピューティング / スケーラブル / 通信同期回避 / 時間方向離散 / 異粒度数値カーネル

【研究成果の概要】

本研究は、数万から数億のコアプロセッサが搭載される計算システム環境下において、過去に蓄積された高性能な数値計算サービスを新しい数学原理に基づき実現することを目的にし、「異粒度数値カーネル構築」と共に「非同期的な数値計算アルゴリズム」の２大テーマのもと、１）非同期的数値計算アルゴリズムに関する理論と実用レベルにある省通信・省同期アルゴリズムについて研究しCAHTRやFDTD向けの手法を提案した。更に、２）超メニイコアでのスケーラブルな軽量コード生成のための自動チューニングなどの核基盤技術研究を推進し次世代数値計算ソフトウェアの新技術創出に繋がる新機軸探究を進めた。

【研究種目】基盤研究(B)

【研究期間】2015-04-01 - 2018-03-31

【配分額】18,330千円 (直接経費: 14,100千円、間接経費: 4,230千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】22540115 (KAKENデータベースで見る）

【研究キーワード】

確率微分方程式 / 弱近似 / シミュレーション / 数理ファイナンス / 金融派生商品 / 高頻度取引 / 数値計算 / 確率論 / 準モンテカルロ / 数理工学 / アルゴリズム

【研究成果の概要】

確率微分方程式(以下SDE)の高次弱近似を実現するアルゴリズムと理論に関するものである. 以下の5点の成果を得た. [1]バリア型の金融派生商品への楠岡近似アルゴリズムの拡張. [2]我々の楠岡近似のアルゴリズムの計算機プログラムライブラリの完成. [3]SDEの7次の弱近似(通常の意味では3次)を実現する新しい近似アルゴリズムの発見. [4]ファイナンスに於いて重要であるHeston Modelに我々のアルゴリズムの一つ(所謂NNアルゴリズム)を適用する際に更に高速化を可能とするような変数変換手法の発見. [5]高頻度取引の分野で情報に時差がある場合にそれを検出する指標を新たに発見.

【研究種目】基盤研究(C)

【研究期間】2010-04-01 - 2014-03-31

【配分額】3,900千円 (直接経費: 3,000千円、間接経費: 900千円)

【研究分野】工学基礎

【研究領域課題番号】21360045 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 凸関数 / 双対性 / 劣モジュラ関数 / マトロイド / 数理工学 / 最適化 / アルゴリズム

【研究成果の概要】

工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」に よって統合する研究を行った．離散凸解析の理論と応用を， 連続・離散軸，凸・非凸軸，分野横断軸，の３つの観点から整理することによって，個々の数 理的技法や応用諸問題の相互関係を明確にし，数理の深化，応用の開拓，ソフト ウェアの整備の３つの観点から研究を行い，新たな展開を達成した．とくに，数理の深化については，Ｌ凸関数最小化アルゴリズムの詳細な解析やＤＣ計画の枠組みの提示などの成果をあげた．

【研究種目】基盤研究(B)

【研究期間】2009-04-01 - 2015-03-31

【配分額】17,810千円 (直接経費: 13,700千円、間接経費: 4,110千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】18651076 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / スポーツマネジメント / スケジューリング / 半正定値計画 / 数理工学 / オペレーションズ・リサーチ

【研究成果の概要】

1.一様な巡回トーナメント問題に関する近似法 本拠地間の距離が一様な巡回トーナメント問題に対し、移動距離(回数)最小化問題に対するトーナメントスケジュールの作成法を、平成18年度国際会議の論文特集号(Lecture Notes in Computer Science)に本年投稿し、採択された。本手法は,カークマンスケジュールと呼ばれる特殊なスケジュールを改変することで,2重総当たり戦の移動回数最小化問題の良質な解を構築する.本手法によって、最適解に非常に近い解が得られることを,理論的に保証した.提案手法により,2重総当たり戦の移動回数最小化問題について,チーム数22,28,34,40,46の場合には既存の世界記録を凌駕する新たな解が得られ,さらに得られた解は最適解であることを保証することに成功した。
2.半正定値計画緩和に基づく試合場決定問題の解法
試合場決問題について、半正値計画緩和と、形計画緩和に基づく解法の提案を行った。(この結果は、Pacif1c Joumal of Optimizationに採択されている。)両手法について、1重と2重総当たり戦の両方の問題に適用する計算実験を行った。その結果、1重総当り戦では、線形計画緩和に基づく方法は、殆どの問題例において最適解を生成する事が確認された。2重総当たり戦では、線形計画緩和に基づく方法では、劣悪な解しか得られないことが判明した。これに対し半正定値計画緩和に基づく方法は、どの問題例でも高品質の解を生成することが確認された。半正定値計画緩和は、計算時間の短縮が検討課題として残されている。

【研究種目】萌芽研究

【研究期間】2006 - 2007

【配分額】2,500千円 (直接経費: 2,500千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】18540113 (KAKENデータベースで見る）

【研究キーワード】

確率論 / 数理工学 / アルゴリズム / 数理ファイナンス / デリバティブ / 確率微分方程式 / 確率諭

【研究成果の概要】

(1)楠岡近似の原理に従って確率微分方程式で記述される拡散過程の高次弱近似を可能とする、頑健で汎用的な数値計算アルゴリズムを発見・構成した。(2)数理ファイナンスへの応用によりその有用性:(a)計算の劇的な高速化(b)頑健な離散化の実現(c)汎用性、を検証した。(3)そのアルゴリズムが広く社会に受け入れられるように計算機プログラムを開発した。

【研究種目】基盤研究(C)

【研究期間】2006 - 2009

【配分額】3,630千円 (直接経費: 3,000千円、間接経費: 630千円)

【研究分野】情報学基礎

【研究領域課題番号】15300004 (KAKENデータベースで見る）

【研究キーワード】

暗号認証等 / アルゴリズム / 情報基礎 / 数理工学 / 情報システム / 楕円曲線暗号 / 実装攻撃 / 公開鍵暗号 / 離散対数 / XTR / 電力解析 / 暗号 / 情報セキュリティ / RSA暗号 / サイドチャネル攻撃 / 実装解析 / 高速実装

【研究成果の概要】

(1)楕円曲線暗号において、個別に議論されてきたサイドチャネル攻撃およびその防御法を、攻撃者の能力に関する仮定を明らかにした上で、事前計算テーブルの有無に着目し体系的に類別した。この分類を基にして、サイドチャネル攻撃に対する防御法の構成に対して、メモリと速度の観点から統一的見通しを与えた。
次にサイドチャネル攻撃に対する、事前計算テーブルを用いる新たな防御法として、wNAF(Width-w Non-Adjacent Form、幅w非隣接形式)法を用いた防御法を提案し、その安全性・効率性の解析を行なった。この防御法は、メモリと速度のトレードオフの関係において、最適であることも理論的に示した。
また、べき指数展開処理時に漏洩するサイドチャネル情報を用いて秘密べき指数を導出する方法について考察し、wNAF展開、fractional window展開については、SPAなどによりべき指数展開処理の実行シーケンスの特徴が検出できた場合に、観測した実行シーケンスから秘密べき指数を導出するアルゴリズムを構成した。
(2)楕円曲線暗号に対する実装攻撃の防御法として、Randomized Binary Signed Digitsとよばれる手法が提案されていたが、この防御法の不完全性を明らかした。
また、XTRとよばれる特殊な離散対数問題を利用した公開鍵暗号に対する実装攻撃の理論解析を行い、その防御法も検討した。その上で、XTRと楕円曲線暗号との性能比較を行った。
(3)代表的なKoblitz曲線を用いた公開鍵暗号に対する実装攻撃の理論分類・評価と同時に、実験的検証も試みた。特に、実装攻撃に対する2つの新しい防御法を提案した。2つの手法とも、単純電力解析に耐性を持つように固定パターン再符号化を利用するものである。プロジェクト最後の年であり、これまでの研究成果を整理し、残された検討課題を議論した。特にRFIDなどの現実のユビキタスシステムにおける実装環境での攻撃とその対策も考察した。

【研究種目】基盤研究(B)

【研究期間】2003 - 2005

【配分額】14,000千円 (直接経費: 14,000千円)