組合せ的前処理と量子アニーリングの融合による行列計算の加速手法

组合预处理与量子退火相结合加速矩阵计算的方法

基本信息

  • 批准号:
    22K19772
  • 负责人:
  • 金额:
    $ 3.83万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for Challenging Research (Exploratory)
  • 财政年份:
    2022
  • 资助国家:
    日本
  • 起止时间:
    2022-06-30 至 2025-03-31
  • 项目状态:
    未结题

项目摘要

近年,量子アニーリングが注目を集めている.量子アニーリングは,量子揺らぎを利用した物理過程によって最適化問題の解を求める手法であり,様々な組合せ最適化問題を高速に解けると期待されている.量子アニーリングマシンは,ゲート型の量子計算機に比べて大規模化が容易であり,例えばD-Wave社2000Qシステムでは,0-1変数で最大2000変数を持つ組合せ最適化問題(0-1変数無制約2次計画問題)の求解が可能である.本研究では,量子アニーリングマシンと古典計算機を組み合わせたハイブリッド環境により,行列の対角化(固有値計算)や連立1次方程式の求解などの応用上重要な行列計算を加速することを目的としている.そのための手法として,本研究では組合せ的前処理と量子アニーリングを融合する.多くの行列計算アルゴリズムは,行列要素の絶対値の分布や非ゼロ要素の分布により,収束性や計算量が大きく変化する.そこで,行と列の置換などの組合せ的前処理により,これらの分布を対象アルゴリズムの特性に合わせて最適化すれば,収束性の向上や計算量の減少が見込める.今年度の研究では,実対称行列向けの固有値解法であるブロックヤコビ法を対象として,効率的な組合せ的前処理の設計と評価を行った.具体的には,ブロックヤコビ法における非対角ブロックの消去前に,行と列の置換により,絶対値の大きい要素を対角ブロックに集中させ,消去が効率的に行えるようにした.本前処理を組合せ最適化問題として定式化し,量子アニーリングマシンD-WAVE Advantage上で実装して12×12程度の小規模行列に適用したところ,絶対値の大きい要素の対角ブロックへの集中が正しく行えることを確認した.
近年来,量子退火引起了人们的关注。量子动物是一种根据量子波动的物理过程,需要解决优化问题的方法,并有望在高速下解决各种组合优化问题。量子退火机比栅极型量子计算器更容易增加大小)。在这项研究中,目的是在结合量子动物机器和经典计算机的混合环境中加速应用应用中的重要矩阵计算。作为一种方法,本研究结合了组合预处理和量子动物。由于矩阵元素的绝对值和非零元件的分布,许多矩阵计算算法发生了显着变化。因此,如果通过组合预处理(例如更换行和列)根据目标算法的特性优化了这些分布,则可以预期收敛和计算下降。在今年的研究中,我们评估了块雅各布方法的预处理的有效组合,这是实际格式矩阵的独特价值解决方案。具体而言,在jacobo方法中擦除非核对角块之前,通过更换行和列来将绝对值的元素集中在对角线块上,以便可以有效地删除它们。格式化设置为优化问题,并在量子动物机D-Wave Adveage上实现,并应用于约12x2的小基质,并且绝对大元素的对角线块上的浓度集中在对角线块上。我确认可以正确完成。

项目成果

期刊论文数量(10)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Error analysis of the truncated Taylor series expansion method for computing matrix exponential
计算矩阵指数的截断泰勒级数展开法的误差分析
  • DOI:
    10.14495/jsiaml.14.147
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0.4
  • 作者:
    Yamamoto Yusaku;Kudo Shuhei;Hoshi Takeo
  • 通讯作者:
    Hoshi Takeo
Discrete relativistic Toda equation from the perspective of shifted LR transformation
移位LR变换视角下的离散相对论Toda方程
  • DOI:
    10.1016/j.physd.2022.133485
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Yamamoto Yusaku;Minoshita Naoya;Iwasaki Masashi
  • 通讯作者:
    Iwasaki Masashi
二重指数関数型数値積分公式を用いた行列符号関数の計算の改良および応用
双指数数值积分公式计算矩阵符号函数的改进及应用
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    宮下朋也;山本有作
  • 通讯作者:
    山本有作
Convergence to Singular Triplets in the Two-Sided Block-Jacobi SVD Algorithm with Dynamic Ordering
具有动态排序的两侧块-Jacobi SVD 算法中奇异三元组的收敛性
Box and Ball System with Numbered Boxes
带编号盒子的盒子和球系统
  • DOI:
    10.1007/s11040-022-09425-6
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Yamamoto Yusaku;Fukuda Akiko;Kakizaki Sonomi;Ishiwata Emiko;Iwasaki Masashi;Nakamura Yoshimasa
  • 通讯作者:
    Nakamura Yoshimasa
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

山本 有作其他文献

複素非対称行列向け固有値解法のCSX600による高速化
使用CSX600加速复杂非对称矩阵特征值求解方法
  • DOI:
  • 发表时间:
    2007
  • 期刊:
  • 影响因子:
    0
  • 作者:
    宮田 考史;山本 有作;中村 佳正
  • 通讯作者:
    中村 佳正
Xeon PhiにおけるDSYRKの並列化手法と性能解析
DSYRK在Xeon Phi上的并行化方法及性能分析
SMP上での並列QR分解に対する自動チューニングの検討
SMP并行QR分解自动调优研究
  • DOI:
  • 发表时间:
    2012
  • 期刊:
  • 影响因子:
    0
  • 作者:
    深谷 猛;山本 有作;張 紹良
  • 通讯作者:
    張 紹良
Oakforest-PACSにおける一般化固有値計算の性能解析と性能予測
Oakforest-PACS中广义特征值计算的性能分析及性能预测
  • DOI:
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0
  • 作者:
    星健夫;福本智哉;深谷猛;山本 有作
  • 通讯作者:
    山本 有作
対称行列向けマルチシフトQR法及び漸近的収束性解析
对称矩阵的多移QR方法和渐近收敛分析
  • DOI:
  • 发表时间:
    2007
  • 期刊:
  • 影响因子:
    0
  • 作者:
    宮田 考史;岩崎 雅吏;山本 有作;張 紹良
  • 通讯作者:
    張 紹良

山本 有作的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('山本 有作', 18)}}的其他基金

高いスケーリング性能と高精度性を併せ持つ次世代固有値・特異値分解ライブラリの開発
开发结合了高缩放性能和高精度的下一代特征值/奇异值分解库
  • 批准号:
    19KK0255
  • 财政年份:
    2019
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Fund for the Promotion of Joint International Research (Fostering Joint International Research (B))
高速多重極子展開法を用いた派生証券の高速価格計算手法に関する研究
基于快速多极展开法的衍生证券高速价格计算方法研究
  • 批准号:
    16760053
  • 财政年份:
    2004
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)

相似海外基金

制約付き固有値問題に基づく局所潜在空間生成とその大規模分散データ解析への応用
基于约束特征值问题的局部潜在空间生成及其在大规模分布式数据分析中的应用
  • 批准号:
    23K28101
  • 财政年份:
    2024
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
無限次元固有値問題に対する複素モーメント型解法および数理的リスク回避技術の開発
无限维特征值问题复矩型求解方法及数学风险规避技术开发
  • 批准号:
    23K21673
  • 财政年份:
    2024
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
Fast and accurate algorithms for solving large eigenvalue problems
用于解决大型特征值问题的快速准确的算法
  • 批准号:
    23K11226
  • 财政年份:
    2023
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
巨大次元行列の固有値計算の高並列・高精度シミュレーションの挑戦
大维矩阵特征值计算高度并行高精度模拟挑战
  • 批准号:
    23K11125
  • 财政年份:
    2023
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
疑似多倍長演算による現代アーキテクチャに適した高速な数値計算アルゴリズムの創生
使用伪多精度运算创建适合现代架构的高速数值计算算法
  • 批准号:
    22KJ2741
  • 财政年份:
    2023
  • 资助金额:
    $ 3.83万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了