文献

J-GLOBAL ID：202002212416707261   整理番号：20A1035009

2つの[数式:原文を参照]2部分行列を持つ一般分割行列のランクを計算するための組合せアルゴリズム【JST・京大機械翻訳】

A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 [Formula : see text] 2 Submatrices

著者 (2件)： Hirai Hiroshi (The University of Tokyo, Tokyo, Japan) ,  Iwamasa Yuni (Kyoto University, Kyoto, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12125  ページ： 196-208  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文では,ブロック構造化記号行列(一般的分割行列)[数式:原文を参照]のランクを計算する問題を考察した。ここで,[数式:原文を参照]はフィールド[数式:原文を参照]上の[数式:原文を参照]行列であり,[数式:原文を参照]は[数式:原文を参照]と[数式:原文を参照]に対して不確定である。この問題は,二部マッチング問題の代数的一般化と見なすことができ,岩手とMurota(1995)によって考察された。この問題に関する最近の関心の1つは,Ivanyos,QiaoおよびSubrahamanyam(2018),およびGarg,Gurvit,OlivivaおよびWigderson(2019)による非可換Edmonsの問題との関連にあり,ここでは,このクラスと非可換ランク(ncランク)はこのクラスの記号行列に対して同じである。本論文の主な結果は,サイズ[数式:原文を参照]の[数式:原文を参照]型一般分割行列の記号ランクを計算するための組合せ[数式:原文を参照]時間アルゴリズムである。著者らのアルゴリズムは,一般的な記号行列のncランクに対するIvanyos,Qiao,およびSubrahamanyamによるWongシーケンスアルゴリズムに基づいているが,より単純である。提案したアルゴリズムは,ビットサイズを制限するために,ブローアップ操作,フィールド拡張を必要とせず,追加の注意を必要としない。さらに,それは任意の場[数式:原文を参照]に対するAの最大ランク完了を自然に提供する。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  不確実性 ,  ブロック構造 ,  岩手県
準シソーラス用語： *組合せアルゴリズム ,  ビットサイズ , 【Automatic Indexing@JST】

著者キーワード (3件)： 一般分割行列 ,  Edmondsの問題 ,  非可換Edmonds問題

分類 (3件)： 数値計算  (JE02000J) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： 数式 ,  参照 ,  行列 ,  計算 ,  組合せアルゴリズム