その他の計算機科学 · 2026年11月3日(火)

分散計算、ゲーム理論、情報理論など。

RSS で購読
arXiv cs.DS · cs.DB · cs.DC

A GPU Engine for Sparse Matrix-Vector Products on k²-Tree-Compressed Graphs

説明k²木で圧縮されたグラフに対する疎行列・ベクトル積のGPUエンジン

要約本論文は、ブール行列を圧縮して格納するk²木(k²-tree)上で、GPUによる疎行列・ベクトル積を行う手法を提案する。木を階層ごとに並列に降下し、子ノードの位置を並列プレフィックスサムまたはサンプリングされたディレクトリで求め、タイル単位で処理して一時メモリを木の深さで抑える。NVIDIA GB10とH100で最大12億辺の14個のグラフを評価し、木はcuSPARSEのCSRより2.3〜27倍小さく、12億辺のグラフでは積の実行に必要なデバイスメモリがcuSPARSEより9倍少ない1.1 GBであったと報告している。

Francesco Tosoni, Gabriele Mencagli

arXiv cs.IT · math.CO · math.IT

Uniform Sampling of Linear Codes with Prescribed Hull Dimension

説明指定されたhull次元を持つ線形符号の一様サンプリング

要約本論文は、指定されたhull次元を持つ線形符号に対する厳密な一様サンプラーを与える。対象はユークリッド内積、エルミート内積、シンプレクティック内積で、あらゆる標数の有限体を扱う。奇標数体上のユークリッド内積の場合を除き、任意の指定hull次元に対する初の一様サンプラーである。各サンプルの期待計算量は、F_qまたはF_{q^2}上のN次元空間内の次元k符号に対して O(k²N + k log q) 回の体演算である。

Keita Ishizuka

arXiv cs.IT · math.IT

An information-geometric formulation of distributed computation

説明情報幾何学に基づく分散計算の定式化

要約本論文は、個々の構成要素の寄与に還元できない集団的な計算を捉えるための情報動態の幾何学的理論ΦID^IGを提案しています。多入力多出力の演算を解釈可能な計算モードに完全分解し、離散系とガウス系で既知の正解を用いて検証しています。さらに、カオス写像、100種以上の哺乳類の脳構造、金融市場に適用し、それぞれの計算構造の特徴を示しています。

Alberto Liardi, George Blackburne, Pedro A.M. Mediano

arXiv cs.IT · cs.SY · eess.SY

Beyond GNSS: Leveraging LEO Satellite Signals of Opportunity for Doppler Positioning

説明GNSSを超えて:低軌道衛星の機会信号を用いたドップラー測位

要約低軌道衛星コンステレーションは移動が速く、大きなドップラーシフトを生じます。本論文は、このシフトを利用して利用者端末を測位する方法を扱い、特にGNSSが使えない環境での有用性に注目しています。機会信号の原理、課題、関連技術を整理するとともに、Sionnaをベースにした非地上系ネットワーク向けレイトレーシングの枠組みSionnaNTN-RTを提案しています。シミュレーションでは、都市部と開けた空の両方で高い測位精度が得られることが示されています。

Md. Ali Hasan, M. Humayun Kabir, Sangmin Han ほか

arXiv eess.IV · cs.DC · cs.NA

Scaling global tractography with ExaTract: from large cohorts to ultra-high-resolution datasets

説明ExaTract による全脳トラクトグラフィーの大規模化:大規模コホートから超高解像度データセットまで

要約本論文は、高性能計算(HPC)アーキテクチャ向けに設計された並列化スピングラス型トラクトグラフィーフレームワーク「ExaTract」を提案し、オープンソースのMPI+Kokkosアプリケーションとして実装している。トラクトグラフィーの領域を空間的に重なり合う部分領域に分割して分散メモリノード上で処理し、境界部分の変更を定期的に同期させることで大域的な収束性を保つ。体内および体外の拡散MRIデータで検証を行い、完全なHCPデータセットでは集団規模のスループットを示し、高解像度のChenonceauデータセットでは全脳トラクトグラフィーによる初のメソスコピックな構造コネクトームを提供している。

Simon Legeay, Felix Matuschke, Bastien Herlin ほか

arXiv cs.GT · econ.TH

On inverse aggregate network assignment games

説明逆向集約ネットワーク割当ゲームについて

要約複数の事業者が共有ネットワーク上で運営とインフラを調整する移動市場において、事業者と利用者の行動を理解するための集約型ネットワーク割当ゲームを論じる。経路ベースとPURCベースの定式化と解法を提案し、リンクベースの定式化に対する逆最適化モデルを示す。長島鉄道(LIRR)のネットワーク(897ノード、8,320有向リンク)を用いた校正により、リンクの一部のみを観測した場合でも実際のリンク流量をよく再現できることを示している。

Joseph Y. J. Chow

★★★★☆ 注目
arXiv cs.GT

At What Cost? (In)efficiency in First-Price Procurement Auctions

説明どれほどの代価か?一価購買オークションにおける(非)効率性

要約本論文は、一価購買オークションにおけるベイズ・ナッシュ均衡の効率性を研究し、均衡における期待社会的費用と社会最適配分の最小期待社会的費用の比であるPoA(無秩序の代価)で効率を測定する。標準的な一価購買オークションには有界なPoAの保証がないことを示し、有限の保証を回復するため「幻影入札者」の仕組みを提案している。

注目点標準的な一位価格調達オークションのPoAは有界でないことを示し、タイトな界と幻影入札者機構、ほぼ最適な下界を与える。

Simone Palazzotto, Andr\'es Cristi

arXiv cs.IT · cs.SY · eess.SP

Non-Coherent Over-the-Air Distributed Consensus: Algorithm Design and Power Control Optimization

説明非コヒーレント空中分散合意:アルゴリズム設計と送信電力制御の最適化

要約本論文は、瞬時のチャネル状態情報や位相整合を必要としない非コヒーレント空中(NCOTA)合意フレームワークを提案し、無線ネットワークにおける分散平均合意を扱います。行確率的混合に対応する分散投影勾配降下法(DPGD-RS)を設計し、各ノードの初期状態の正確な平均値への平均二乗収束を示しています。さらに、平均二乗合意誤差の閉形式上界を導出し、送信電力と受信スケーリング係数を同時に最適化する手法を提案して、数値結果で全電力送信やスペクトル半径最小化の基準法より収束が速いことを確認しています。

Yuhang Deng, Zheng Chen, and Erik G. Larsson

arXiv cs.IT · math.IT · math.NT

Good rational functions up to degree six

説明次数6以下の良い有理関数の分類

要約局所回復可能符号(LRC)は分散ストレージシステムの基礎となる符号です。本論文は、標数2において次数6以下の良い有理関数を完全に分類しています。代数関数体論を用いて、これらの低次数の場合について最小の算術的および幾何学的ガロア群を明示的に求めています。さらに、拡大体上の完全分解する位置の正確な個数が線形漸化式列に従うことを示し、対応する最適LRCの正確な長さと次元を効率よく計算する方法を与えています。

Anuvrat Jaindungarwal, Divyesh Vaghasiya

arXiv cs.SE · cs.DC

uTECH Turbo-MOVES: The Intersection of Software Architectural Innovation and Sustainable Mobility Analysis

説明uTECH Turbo-MOVES:ソフトウェア設計の革新と持続可能なモビリティ分析の融合

要約本論文は、米国環境保護庁の自動車排出量シミュレータ(MOVES)の計算を高速化するソフトウェアアーキテクチャ「uTECH Turbo-MOVES」を紹介している。MOVESのCalculatorモジュールや入出力構造は変更していない。RunSpecの分割、コンテナ分離、メモリ内での中間データ保存、並行処理の制御を組み合わせて実行効率を高めている。6つのベンチマークで評価し、Default規模の1回の実行は実測5.5倍、推定15.3倍の高速化、8郡の排出率分析では全体で84.8倍の高速化を示した。

Cafer Avc{\i}, Alireza Yazdiani, Roopak Srinivasan ほか