野呂　正行
立教大学理学部数学科
教授
ホームページ E-mail: noro@rikkyo.ac.jp Tel: 03-3985-2494

研究テーマ：

計算代数システムの開発および計算代数アルゴリズムの研究.

何を研究してきたか：

計算代数システムは, 計算機上で主として数学のための計算を誤差なしで正確 に行うためのソフトウェアです. ある対象の存在が数学で示されていても, その計算が有限の手間でできるとは 限りません. さらに, 有限の手間で計算するアルゴリズムが与えられていても,そ のアルゴリズムの実行が計算機を用いてもとてつもなく時間がかかる場合もあ ります. 私は, 計算代数システムである Risa/Asir を開発するとともに,主として計算 効率の観点から, 既存アルゴリズムの改良, 新アルゴリズムの研究開発を行い, いくつかの成果を得ました. 特に, 多項式因数分解とグレブナー基底の計算の 効率化についていくつかの結果を得て, その効果は Risa/Asir 上で実証されて います. また, これらの応用として,多項式イデアルの効率よい分解アルゴリズ ム, あるいは D-加群に関連する種々の演算アルゴリズムの研究も行っています また, 世の中に数多くある数学ソフトウェアを結合してさまざまな計算を行う ためのプロトコルである OpenXM に関する研究開発を高山信毅氏(神戸大理)と 共同で行っています.

現在までに何ができたか：

  1. 計算機代数システム Risa/Asir
    2. Risa/Asir は, 主として有理数および有限体係数の多項式を扱うための計算機 代数システムで, その開発は, 2000 年 8 月までは富士通(株)および(株)富士 通研究所において行われ, 2000 年 9 月以降は主として神戸大学において継続 中です.
    現在実現されている機能としては, 数および多項式の四則, GCD, 因数分解, 多項式の最小分解体計算, Galois 群計算, 多項式環および多項式を係数とする 微分作用素環である Weyl 代数におけるグレブナー基底計算, イデアルの交わり, 商などの諸演算, 準素分解, 多項式の b-関数計算, 2 変数多項式の実零点表示などがあります. また, Risa/Asir 上のユーザ言語でのプログラミング支援のためのデバッガ が組み込まれています. グレブナー基底計算において特徴的なのは, 有理数体上の結果を得るために, 有限体上での計算および Hensel構成を 多用していることです. 理論的部分は以下の論文 2 によりますが, この方法に より, 結果の大きさに応じた時間, 空間計算量での計算という目標がある程度 達成されています.
    Risa/Asir の開発目標の一つに代数方程式系の代数的方法による求解がありま す. グレブナー基底計算と多項式因数分解はこれを実現するための主要な機能 です. 計算機上で代数方程式を解くというと, 数値解法を思い浮かべる人が多 いと思います. 実際, 浮動小数による近似解を求める方法として, さまざまな 数値解法が考案され, グレブナー基底による方法より随分と効率よく数値解が 求まる場合もあります. しかし, 数学に現れる問題の場合, ほしいのは厳密解, または解の満たす代数的な関係式である場合が多く, そのような目的には数値 解では不十分です. 経験上, 数学で現れる問題の場合には, 得られる結果もコ ンパクトできれいなものの場合が多く, そのようなものに対しては, グレブナー 基底計算, 準素分解などが有効に働き, 効率よく厳密解が求まる場合がありま す. しかし, そのような場合でも, 算法, 実装方法によっては求まるものも求 まりません. できるだけ大規模な計算が高速にできるよう, 実装方法について も随所に工夫があります.
    有限体上の計算は, 標数 0 の演算を効率よく実行するための手段として大変 重要です. これは, 計算代数の算法の多くは, 有限体上での結果をテンプレー トとして, Hensel lifting や Chinese remainder theorem などで元の体での 結果を復元する (modular 算法と呼ばれる), という形だからです. また, RSA, 楕円曲線暗号, 正標数の代数幾何, 符号理論との関係で, 有限体上の計 算そのもの興味の対象です. このような計算をサポートするために, 扱う有限 体の特性 (標数 2 or 奇素数, 素体 or 拡大体, 体の位数が大 or 小 etc.) に応じてさまざまな表現をもつ有限体を扱うことができます.
    Risa/Asir のソースコードは 2000 年より free 化されました. それまでは, バイナリのみ free ということで, 内部が black box であるソフトウェアは 信用できない, と使ってもらえない場合もありましたが, いましたが, ソース コードさえ読めればそのような心配はないわけです. (もっとも, 読んだ上で 使ってもらえないという場合もあり得ますが..)

  2. 算法研究
    • グレブナー基底計算への modular 計算の応用
      • 主として, 有理数体上のグレブナー基底演算, change of ordering, RUR (rational univariate representation) の計算をmodular 計算により効率化 することを目指して. いくつかの結果を得ました.
    • 多項式因数分解
      • 位数の小さい有限体上の2 変数多項式の効率よい分解アルゴリズムを 開発しました. 有限体のを原始根により表現することで, 拡大が必要になっても効率を 落とさないようにする 実装上の工夫と, 1 変数で extraneous factor を多く持つ場合に, change of ordering を応用した真の因子計算を行う多項式時間算法の組み合わせによる ものです.
    • b-関数の計算
      • 多項式の大域 b-関数の計算法として知られる, 大阿久-高山の算 法に, change of ordering および modular 計算を応用して大域 b-関数の計算を 高速化し, これまでのアルゴリズムでは計算が事実上不可能だったような 例も計算機上で計算できるようになりました. さらに, 局所 b-関数に 関しても, 同じ局所 b-関数を与える点の集合を空間の stratification として 与えるアルゴリズムを開発し実装しました.
    • イデアル分解アルゴリズム
      • 位数の小さい有限体上多項式イデアルの根基の素イデアル分解アルゴリズムを開発 しました. 位数の小さい有限体上では, separating element (原始元の一般化) を与えるような不定元の線形和が作れない場合がありますが, これを, 有限体 を代数拡大することで解決しました. また, 最近, 下山ー横山による準素分解 アルゴリズムをベースに, 計算途中に冗長な成分を全く生成しない準素分解 アルゴリズムを開発しました.


  3. 分散並列計算およびOpenXM
    4. 計算機代数システムを使う場合, 浮動小数を用いた数値計算と異なり, 計算時 間や所要メモリ量が予期できない場合がしばしばあります. これらをいかに小 さく押えるかが, 算法研究および実装の工夫にかかってくるわけですが, それ にも限界があります. 分散並列計算はそのような困難を打破する方法の一つで す. この場合, 通常は同一のシステムを複数用いて, データあるいはタスクを 分割し, 通信しながら計算を行いますが, 計算効率向上よりは, 作業上の効率 向上のために, 異なるシステムをネットワーク上で結合して, 単体のシステム では困難な計算を実行する, という場合もあります. OpenXM は, これら双方 の目的を達成するための通信規約(プロトコル)です.
    Risa/Asir においては, 主として前者の目的のために独自プロトコルを定義し, それにより, グレブナー基底計算の代表的算法である Buchberger 算法の並列化 を行うなどしてきましたが, 高山氏の Kan/sm1 との結合をきっかけに, 汎用 プロトコルを検討しはしめ, 現在では, Risa/Asir, Kan/sm1 をはじめとして さまざまな数学ソフトの相互呼出しができるようになってきています.

これから：

  1. Risa/Asir

    2. 計算機代数システムの, 数学特に代数幾何, 数論に対する有用性は多くの人が 認めるところだと思います(異論はあると思いますが). 以前は, 数学者でも 商用の汎用システムである Maple, Mathematica などを使って研究している人が 多かったのですが, 最近は, Macaulay2, Singular などを使う人も増えています. これらは, Risa/Asir と同様ソースコードまでフリーなソフトウェアです. これらに比べると, Risa/Asir は後発でマイナーですが, フリーであるという 利点を生かし, 必要があれば Macaulay2, Singular で使われているアイディア も取り入れつつ, 有用, 高速かつオープンな計算機代数システムを作り上げていきたいと考えて います.

  2. 分散並列計算および OpenXM

    3. OpenXM については, 現状では計算機能を提供するシステム (サーバ), あるい はサーバを呼び出せるシステム(クライアント)を増やしながらプロトコルの修 正, 追加を行っている段階です. これが一段落したら, 何らかの形で広くプロ トコルを公開し, OpenXM への一般参加を募り, サーバ, クライアントの種類 をさらに増やす必要があります. 一方で, OpenXM により可能になる数学的に 高度な計算例を見付けることも重要です.
    分散並列計算に関しては, Risa/Asir の既存機能の並列化に関連して, LAPACK, ScaLAPACK などの数値計算ライブラリの提供する機能を, 有限体上の 計算に対して提供できるライブラリの開発を計画しています. これは, グレブ ナ基底変換や, 次項で述べる F4 算法などを並列化する場合に, 有限体上の大 規模行列演算の並列化が必要になるためです. このようなライブラリは汎用性 があるため, 単独でさまざまな用途に用いられる可能性があります.

  3. 算法研究

    4. 任意入力イデアルからのグレブナー基底計算法は Buchberger 算法がほぼ唯一の 方法でしたが, 1997年に J.C. Faugere (Pari VI) により F4 算法が提案され ました. この方法は確かに高速化の可能性を持つものの, 実装の詳細は明らか にされておらず, 彼自身の示すデータ並の高速化はまだ他には得られていない ようです. しかし, この方法は十分に検討の価値があると考え, F4 の検証, 改良あるいは並列化, 微分作用素環への応用を進めていきたいと考えています. また, グレブナー基底変換, 準素分解につき係数体を有理数体係数から代数体, 有限体, 有理関数体などに拡張した場合に効率よく計算できる算法を考案した いと考えています.
    以上とは別の方向として, 第三者による検証可能な結果を与える算法の考察が あります. これは, 計算機代数システムを, 楽屋裏での計算ツール以上のもの とする試みです. 一例として, グレブナー基底計算の検証データの提供がありま す. イデアル I のグレブナー基底の元 g は, I の生成元 f1,...,fm により生 成されているはずですが, 生成関係式が示されない場合, g がI に属する保証 はありません. この場合, f1,...,fm から g に至る, 単項式係数の積和によ る履歴を与えることで, 他のシステムで生成関係を確認することができま す. このように, どのようなシステムでも実行でき, かつ信頼性のある演算の 組合せを検証データとして提供することを, さまざまな算法に対して考察する のです.
    イデアル分解については, かなり満足のいくアルゴリズムが得られました. しかし, このアルゴリズムは, イデアルの根基の素イデアル分解を基礎 にしており, このアルゴリズムの効率が全体の効率を左右します. これに 関しては, 残念ながらまだ場合により計算が滞ってしまう場合があります. これを, できるだけ広い入力に対してスムーズに行えるように改良して いくことが大変重要です.

主な業績
  1. (with T. Takeshima, K. Yokoyama, T. Shimoyama, H. Anai, H. Murao, K. Ohara) A Computer Algebra System Risa/Asir , 1994-2011.
  2. (with T. Kawazoe) Algorithms for computing a primary ideal decomposition without producing intermediate redundant components, Journal of Symbolic Computation, in Press (2011).
  3. New Algorithms for Computing Primary Decomposition of Polynomial Ideals, Proceedings of ICMS2010, LNCS6327, Springer, 233-244 (2010).
  4. (with K. Nishiyama) Stratification associated with local b-functions, Journal of Symbolic Computation, 45. 462-480 (2010).
  5. Modular Algorithms for Computing a Generating Set of the Syzygy Module, Proceedings of CASC2009, LNCS 7543 Springer, 259-268 (2009).
  6. (with T. Sasaki, K. Yamada, M. Yoshida) Confluence of Swallowtail Singularities of the Hyperbolic Schwarz Map Defined by the Hypergeometric Differential Equation, Experimental Math. Vol. 17, No. 2 (2008).
  7. (with M. Kaneko, K. Tsurumaki) On a conjecture for the dimension of the space of the multiple zeta values, IMA Volume 148 ``Software for algebraic geometry'', Springer 47-58 (2008).
  8. (with Y. Kurata) Computation of Discrete Comprehensive Groebner Bases Using Modular Dynamic Evaluation, Proceedings of ISSAC2007, ACM Press, 243-250 (2007).
  9. An efficient implementation for computing Groebner bases over algebraic number fields, Proceedings of ICMS2006, LNCS4151, Springer, 99-106 (2006).
  10. Modular Dynamic Evaluation, Proceedings of ISSAC 2006, ACM Press, 262-268 (2006).
  11. (with K. Kimura) Automatic weight generator for the Buchberger algorithm, Proceedings of MACIS2006, 33-44 (2006).
  12. (with Y. Kawano, K. Kimura, H. Sekigawa, K. Shirayanagi, M. Kitagawa, M. Ozawa) Existence of the exact CNOT on a quantum computer with the exchange interaction, Quantum Ioformation Processing 4(2), 65-85 (2005).
  13. Dynamic Evaluation の実装について, 数式処理, Vol. 11, No. 3,4, 21-28 (2005).
  14. (with K. Yokoyama) Implementation of prime decomposition of polynomial ideals over small finite fields, Journal of Symbolic Computation, 38, 1227-1246 (2004).
  15. A Computer Algebra System: Risa/Asir, Algebra, Geometry and Software Systems, M. Joswig and N. Takayama (eds.), Springer, 147-162 (2003).
  16. (with K. Yokoyama) グレブナー基底の計算 基礎篇 計算代数入門. 東京大学出版会 (2003).
  17. An Efficient Modular Algorithm for Computing the Global b-function. Proceedings of ICMS2002, World Scientific, 147-157 (2002).
  18. (with K. Yokoyama) Yet Another Practical Implementation of Polynomial Factorization over Finite Fields. Proceedings of ISSAC2002, ACM Press, 200-206 (2002).
  19. A Computer Algebra System Risa/Asir. Algebra, Geometry and Software, M. Joswig and N. Takayama (eds.), Springer, 147-162 (2002).
  20. (with M. Maekawa, N. Takayama, Y. Tamura) The Design and Implementation of OpenXM-RFC 100 and 101. Computer Mathematics (Proc. ASCM2001), World Scientific, 102-111 (2001).
  21. 計算機代数. Rokko Lectures in Math. 9, 神戸大学理学部数学教室 (2001).
  22. (with K. Yokoyama) A Modular Method to Compute the Rational Univariate Representation of Zero-Dimensional Ideals. Journal of Symbolic Computation, 28, 1, 243-263 (1999).
  23. (with T. Izu, J. Kogure and K. Yokoyama) Efficient implementation of Schoof's algorithm. LNCS 1514 (Proc. ASIACRYPT'98), Springer, 66-79 (1998).
  24. (with J. McKay) Computation of replicable functions on Risa/Asir. Proceedings of the Second International Symposyum on Symbolic Computation PASCO'97, ACM Press, 130-138 (1997).
  25. (with H. Anai and K. Yokoyama) Computation of the Splitting fields and the Galois Groups of Polynomials. Algorithms in Algebraic geometry and Applications, Birkh\"auser (Proc. MEGA '94), 29-50 (1996).
  26. (with T. Takeshima) Risa/Asir -- A Computer Algebra System. Proc. ISSAC '92, ACM Press, 387-396 (1992).