SEARCH
検索詳細岩田 覚 (イワタ サトル)
| 総合イノベーション創発機構化学反応創成研究拠点 | 特任教授 |
研究者基本情報
■ 学位■ URL
researchmap URLホームページURL■ ID 各種
研究者番号
- 00263161
経歴
■ 経歴経歴
- 2020年11月 - 現在
北海道大学, 化学反応創成研究拠点, 特任教授, 日本国 - 2013年02月 - 現在
東京大学, 大学院情報理工学系研究科, 教授, 日本国 - 2008年04月 - 2013年01月
京都大学, 数理解析研究所, 教授, 日本国 - 2006年04月 - 2008年03月
京都大学, 数理解析研究所, 助教授・准教授, 日本国 - 2001年04月 - 2007年03月
東京大学, 大学院情報理工学系研究科, 助教授, 日本国 - 2000年04月 - 2001年03月
東京大学, 大学院工学系研究科, 助教授, 日本国 - 1997年04月 - 2000年03月
大阪大学, 大学院基礎工学研究科, 講師・助教授 - 1994年04月 - 1997年03月
京都大学, 数理解析研究所, 助手, 日本国
研究活動情報
■ 受賞- 2026年03月, 日本OR学会, 業績賞
- 2017年06月, ACM SIGACT, Best Paper Award, STOC 2017
- 2007年04月, 文部科学大臣表彰 若手科学者賞
- 2003年08月, MPS & AMS, Fulkerson Prize
- 2002年11月, 日本IBM科学賞
- 2001年04月, 日本OR学会, 文献賞
- 1999年07月, 計測自動制御学会, 論文賞
- 1997年09月, 情報処理学会, 山下記念研究賞
- Biobjective optimization with M-convex functions
Ellen H. Fukuda; Satoru Iwata; Itsuki Nakagawa
Mathematical Programming, 2026年08月12日
研究論文(学術雑誌) - Index Analysis of Differential-Algebraic Equation Models for Electric Circuits with Gyrators
Satoru Iwata; Mizuyo Takamatsu
International Journal of Circuit Theory and Applications, Wiley, 2026年04月04日, [査読有り]
英語, 研究論文(学術雑誌), ABSTRACT
This paper investigates the index of differential‐algebraic equations (DAEs) that arise in modeling of electric circuits with gyrators. A gyrator is a two‐port network element whose constitutive equations are defined by a skew‐symmetric matrix. While the index analysis of DAEs in circuit simulation has been extensively studied, the existing characterizations are not applicable to circuits that include gyrators. For linear time‐invariant circuits with gyrators, we analyze the index of DAEs using a matroid‐theoretic approach. We show that the problem of determining whether DAEs arising from the hybrid analysis have index at most one or not is reduced to a linear matroid parity problem. We also provide a structural characterization for DAEs arising from the modified nodal analysis (MNA), and extend it to nonlinear circuits, generalizing a structural characterization that is well known in the index analysis of the MNA models. - Rate Constant Matrix Contraction Method for Stiff Master Equations with Detailed Balance
Satoru Iwata; Taihei Oki; Shinsaku Sakaue
SIAM Journal on Scientific Computing, 48, 1, A261, A285, 2026年02月28日, [査読有り]
英語, 研究論文(学術雑誌), 44580247;49927104 - Reaction Yield Oscillates over Reaction Time in First-order Chemical Reactions
Yu Harabuchi; Tomohiko Yokoyama; Keisuke Katayama; Satoshi Maeda; Taihei Oki; Satoru Iwata
RSC Advances, 16, 9, 7681, 7686, 2026年02月, [査読有り]
英語, 研究論文(学術雑誌), 49927104;44580247 - Fast and Numerically Stable Implementation of Rate Constant Matrix Contraction Method
Shinichi Hemmi; Iwata Satoru; Oki Taihei
ICIAM2023 Springer Series, 9, 39, Springer Nature Singapore, 2026年01月12日
論文集(書籍)内論文, Abstract
The rate constant matrix contraction (RCMC) method, proposed by Sumiya et al. (2015, 2017), enables efficient and stable simulations of chemical kinetics in large-scale reaction networks. Iwata et al. (2023) reformulated the RCMC method as an algorithm for solving master equations with rate constant matrices satisfying detailed balance. This study focuses on accelerating RCMC by addressing its bottleneck: the greedy selection of steady states, which is equivalent to MAP inference in determinantal point processes (DPPs) under cardinality constraints. LazyFastGreedy, introduced by Hemmi et al. (2022), combines the practically efficient lazy greedy method with the DPP MAP inference but suffers from numerical instability due to wide-ranging reaction time scales in chemical kinetics. We propose modified LazyFastGreedy that mitigates numerical instability by avoiding subtraction of like-sign numbers, leveraging properties of rate constant matrices and connections to Cholesky decomposition. Numerical experiments on real chemical reaction instances demonstrate that the proposed method achieves significant speed improvements while maintaining numerical stability. - Mathematical Framework to Identify Optimal Molecule Based on Virtual Ligand Strategy
Wataru Matsuoka; Ken Hirose; Ren Yamada; Taihei Oki; Satoru Iwata; Satoshi Maeda
Journal of Chemical Information and Modeling, 65, 13, 6913, 6926, American Chemical Society (ACS), 2025年06月13日, [査読有り]
英語, 研究論文(学術雑誌), 44580247;49927104 - Virtual Ligand-Assisted Optimization: A Rational Strategy for Ligand Engineering
Wataru Matsuoka; Taihei Oki; Ren Yamada; Tomohiko Yokoyama; Shinichi Suda; Carla M. Saunders; Bastian Bjerkem Skjelstad; Yu Harabuchi; Natalie Fey; Satoru Iwata; Satoshi Maeda
ACS Catalysis, 14, 21, 16297, 16312, American Chemical Society (ACS), 2024年10月21日, [査読有り]
英語, 研究論文(学術雑誌), 44580247 - Differentiating the Yield of Chemical Reactions Using Parameters in First-Order Kinetic Equations to Identify Elementary Steps That Control the Reactivity from Complicated Reaction Path Networks.
Yu Harabuchi; Tomohiko Yokoyama; Wataru Matsuoka; Taihei Oki; Satoru Iwata; Satoshi Maeda
The Journal of Physical Chemistry. A, 128, 14, 2883, 2890, 2024年04月11日, [査読有り], [国際誌]
英語, 研究論文(学術雑誌), The yield of a chemical reaction is obtained by solving its rate equation. This study introduces an approach for differentiating yields by utilizing the parameters of the rate equation, which is expressed as a first-order linear differential equation. The yield derivative for a specific pair of reactants and products is derived by mathematically expressing the rate constant matrix contraction method, which is a simple kinetic analysis method. The parameters of the rate equation are the Gibbs energies of the intermediates and transition states in the reaction path network used to formulate the rate equation. Thus, our approach for differentiating the yield allows a numerical evaluation of the contribution of energy variation to the yield for each intermediate and transition state in the reaction path network. In other words, a comparison of these values automatically extracts the factors affecting the yield from a complicated reaction path network consisting of numerous reaction paths and intermediates. This study verifies the behavior of the proposed approach through numerical experiments on the reaction path networks of a model system and the Rh-catalyzed hydroformylation reaction. Moreover, the possibility of using this approach for designing ligands in organometallic catalysts is discussed. - Exact solution for minimization of root mean square deviation with G-RMSD to determine molecular similarity
Tomohiro Nabika; Satoru Iwata; Hiroko Satoh
Bulletin of the Chemical Society of Japan, 97, 2024年03月28日, [査読有り]
英語, 研究論文(学術雑誌) - Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
Satoru Iwata; Yu Yokoi
SIAM Journal on Computing, 52, 5, 1230, 1268, Society for Industrial & Applied Mathematics (SIAM), 2023年10月17日, [査読有り]
研究論文(学術雑誌) - Lazy and Fast Greedy MAP Inference for Determinantal Point Process
Shinichi Hemmi; Taihei Oki; Shinsaku Sakaue; Kaito Fujii; Satoru Iwata
Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS '22), 2022年12月, [査読有り]
研究論文(国際会議プロシーディングス) - Selecting Molecules with Diverse Structures and Properties by Maximizing Submodular Functions of Descriptors Learned with Graph Neural Networks
Tomohiro Nakamura; Shinsaku Sakaue; Kaito Fujii; Yu Harabuchi; Satoshi Maeda; Satoru Iwata
Scientific Reports, 12, 1, 1124, Springer Science and Business Media LLC, 2022年01月, [査読有り]
研究論文(学術雑誌), Abstract
Selecting diverse molecules from unexplored areas of chemical space is one of the most important tasks for discovering novel molecules and reactions. This paper proposes a new approach for selecting a subset of diverse molecules from a given molecular list by using two existing techniques studied in machine learning and mathematical optimization: graph neural networks (GNNs) for learning vector representation of molecules and a diverse-selection framework called submodular function maximization. Our method, called SubMo-GNN, first trains a GNN with property prediction tasks, and then the trained GNN transforms molecular graphs into molecular vectors, which capture both properties and structures of molecules. Finally, to obtain a subset of diverse molecules, we define a submodular function, which quantifies the diversity of molecular vectors, and find a subset of molecular vectors with a large submodular function value. This can be done efficiently by using the greedy algorithm, and the diversity of selected molecules measured by the submodular function value is mathematically guaranteed to be at least 63% of that of an optimal selection. We also introduce a new evaluation criterion to measure the diversity of selected molecules based on molecular properties. Computational experiments confirm that our SubMo-GNN successfully selects diverse molecules from the QM9 dataset regarding the property-based criterion, while performing comparably to existing methods regarding standard structure-based criteria. We also demonstrate that SubMo-GNN with a GNN trained on the QM9 dataset can select diverse molecules even from other MoleculeNet datasets whose domains are different from the QM9 dataset. The proposed method enables researchers to obtain diverse sets of molecules for discovering new molecules and novel chemical reactions, and the proposed diversity criterion is useful for discussing the diversity of molecular libraries from a new property-based perspective. - A Weighted Linear Matroid Parity Algorithm
Satoru Iwata; Yusuke Kobayashi
SIAM Journal on Computing, 51, 2, 238, 280, Society for Industrial & Applied Mathematics (SIAM), 2022年, [査読有り], [招待有り]
研究論文(学術雑誌) - A Pfaffian formula for matching polynomials of outerplanar graphs
Satoru Iwata
Optimization Methods and Software, 36, 2-3, 332, 336, Informa UK Limited, 2021年05月, [査読有り], [招待有り]
研究論文(学術雑誌) - G-RMSD: Root Mean Square Deviation Based Method for Three-Dimensional Molecular Similarity Determination
Tomonori Fukutani; Kohei Miyazawa; Satoru Iwata; Hiroko Satoh
Bulletin of the Chemical Society of Japan, 94, 2, 655, 665, The Chemical Society of Japan, 2021年02月, [査読有り], [国際共著]
研究論文(学術雑誌) - Finding a Stable Allocation in Polymatroid Intersection
Satoru Iwata; Yu Yokoi
Mathematics of Operations Research, 45, 1, 63, 85, 2020年02月, [査読有り]
英語, 研究論文(学術雑誌) - A Blossom Algorithm for Maximum Edge-Disjoint T-Paths
Satoru Iwata; Yu Yokoi
Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), 1933, 1944, 2020年01月, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Index Reduction for Differential-Algebraic Equations with Mixed Matrices
Satoru Iwata; Taihei Oki; Mizuyo Takamatsu
Journal of the ACM, 66, 5, 1, 34, 2019年09月, [査読有り]
英語, 研究論文(学術雑誌) - Correction to: Counting Minimum Weight Arborescences (Algorithmica, (2018), 80, 12, (3908-3919), 10.1007/s00453-018-0426-5)
Koyo Hayashi; Satoru Iwata
Algorithmica, 81, 1, 418, Springer New York LLC, 2019年01月15日
英語, 研究論文(学術雑誌) - List Supermodular Coloring
Satoru Iwata; Yu Yokoi
Combinatorica, 38, 6, 1437, 1456, 2018年12月, [査読有り]
英語, 研究論文(学術雑誌) - Counting Minimum Weight Arborescences
Koyo Hayashi; Satoru Iwata
Algorithmica, 80, 12, 3908, 3919, 2018年12月, [査読有り]
英語, 研究論文(学術雑誌) - Index Reduction via Unimodular Transformations
Satoru Iwata; Mizuyo Takamatsu
SIAM Journal on Matrix Analysis and Applications, 39, 3, 1135, 1151, 2018年07月, [査読有り]
英語, 研究論文(学術雑誌) - Index Reduction for Differential-Algebraic Equations with Mixed Matrices
Satoru Iwata; Taihei Oki; Mizuyo Takamatsu
Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, 45, 55, 2018年06月, [査読有り]
研究論文(国際会議プロシーディングス) - Making Bipartite Graphs DM-Irreducible
Kristof Berczi; Satoru Iwata; Jun Kato; Yutaro Yamaguchi
SIAM Journal on Discrete Mathematics, 32, 1, 560, 590, 2018年02月, [査読有り], [国際共著]
英語, 研究論文(学術雑誌) - A Weighted Linear Matroid Parity Algorithm
Satoru Iwata; Yusuke Kobayashi
Proceedings of the Forty-Ninth Annual ACM SIGACT Symposium on Theory of Computing (STOC'17), 264, 276, 2017年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Household Energy Consumption Prediction by Feature Selection of Lifestyle Data
Kosuke Nishida; Akiko Takeda; Satoru Iwata; Mariko Kiho; Isao Nakayama
2017 IEEE International Conference on Smart Grid Communications (SmartGridComm), 235, 240, 2017年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Solving the Trust-Region Subproblem by a Generalized Eigenvalue Problem
Satoru Adachi; Satoru Iwata; Yuji Nakatsukasa; Akiko Takeda
SIAM Journal on Optimization, 27, 1, 269, 291, 2017年, [査読有り]
英語, 研究論文(学術雑誌) - On the Kronecker Canonical Form of Singular Mixed Matrix Pencils
Satoru Iwata; Mizuyo Takamatsu
SIAM Journal on Control and Optimization, 55, 3, 2134, 2150, 2017年, [査読有り]
英語, 研究論文(学術雑誌) - Potential Energy Surface-Based Automatic Deduction of Conformational Transition Networks and Its Application on Quantum Mechanical Landscapes of d-Glucose Conformers
Hiroko Satoh; Tomohiro Oda; Kumiyo Nakakoji; Takeaki Uno; Hiroaki Tanaka; Satoru Iwata; Koichi Ohno
Journal of Chemical Theory and Computation, 12, 5293, 5308, 2016年, [査読有り] - Finding a Stable Allocation in Polymatroid Intersection.
Satoru Iwata; Yu Yokoi
Proceedings of the Thirty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), 1034, 1047, SIAM, 2016年, [査読有り]
研究論文(国際会議プロシーディングス) - Improved Approximation Algorithms for k-Submodular Function Maximization
Satoru Iwata; Shin-ichi Tanigawa; Yuichi Yoshida
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), 404, 413, SIAM, 2016年, [査読有り]
研究論文(国際会議プロシーディングス) - Solving Generalized CDT Problems via Two-Parameter Eigenvalues
Shinsaku Sakaue; Yuji Nakatsukasa; Akiko Takeda; Satoru Iwata
SIAM Journal on Optimization, 26, 3, 1669, 1694, 2016年, [査読有り]
英語, 研究論文(学術雑誌) - Extended Formulations for Sparsity Matroids
Satoru Iwata; Naoyuki Kamiyama; Naoki Katoh; Shuji Kijima; Yoshio Okamoto
Mathematical Programming Series A, 158, 1-2, 565, 574, 2016年, [査読有り]
研究論文(学術雑誌) - "Maizo"-chemistry Project: toward Molecular and Reaction Discovery from Quantum Mechanical Global Reaction Route Mappings
Hiroko Satoh; Tomohiro Oda; Kumiyo Nakakoji; Takeaki Uno; Satoru Iwata; Koichi Ohno
Journal of Computer Chemistry, Japan, 14, 3, 77, 79, 2015年09月, [査読有り]
英語 - Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms
Yutaro Yamaguchi; Anna Ogawa; Akiko Takeda; Satoru Iwata
IEEE Transactions on Smart Grid, 6, 5, 2189, 2199, 2015年09月, [査読有り]
英語, 研究論文(学術雑誌) - Computing the Signed Distance between Overlapping Ellipsoids
Satoru Iwata; Yuji Nakatsukasa; Akiko Takeda
SIAM Journal on Optimization, 25, 4, 2359, 2384, 2015年, [査読有り]
英語, 研究論文(学術雑誌) - Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity
Satoru Iwata; Tibor Jordan
Discrete Optimization, 12, 121, 128, 2014年05月, [査読有り]
英語, 研究論文(学術雑誌) - Global optimization methods for extended fisher discriminant analysis
Satoru Iwata; Yuji Nakatsukasa; Akiko Takeda
Journal of Machine Learning Research, 33, 411, 419, Microtome Publishing, 2014年
英語, 研究論文(国際会議プロシーディングス) - Graph-TSP from Steiner Cycles
Satoru Iwata; Alantha Newman; R. Ravi
WG, 312, 323, 2014年, [査読有り] - Chemical Structure Elucidation from 13C NMR Chemical Shifts: Efficient Data Processing Using Bipartite Matching and Maximal Clique Algorithms
Shungo Koichi; Masaki Arisaka; Hiroyuki Koshino; Atsushi Aoki; Satoru Iwata; Takeaki Uno; Hiroko Satoh
Journal of Chemical Information and Modeling, 54, 1027, 1035, 2014年, [査読有り] - Global Optimization Methods for Extended Fisher Discriminant Analysis
Satoru Iwata; Yuji Nakatsukasa; Akiko Takeda
Artificial Intelligence and Statistics, 33, 411, 419, 2014年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Exact SVM Training by Wolfe's Minimum Norm Point Algorithm
Masashi Kitamura; Akiko Takeda; Satoru Iwata
2014 IEEE International Workshop on Machine Learning for Signal Processing (MLSP), 2014年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms
Yutaro Yamaguchi; Anna Ogawa; Akiko Takeda; Satoru Iwata
2014 IEEE International Conference on Smart Grid Communications (SmartGridComm), 824, 829, 2014年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
Satoru Iwata; Mizuyo Takamatsu
Algorithmica, 66, 2, 346, 368, 2013年06月, [査読有り]
英語, 研究論文(学術雑誌) - Approximating Max-Min Weighted T-joins
Satoru Iwata; Ramamoorthi Ravi
Operations Research Letters, 41, 4, 321, 324, 2013年, [査読有り] - Finding 2-Factors Closer to TSP Tours in Cubic Graphs
Sylvia Boyd; Satoru Iwata; Kenjiro Takazawa
SIAM Journal on Discrete Mathematics, 27, 2, 918, 939, 2013年, [査読有り]
英語, 研究論文(学術雑誌) - Tractability Index of Hybrid Equations for Circuit Simulation
Satoru Iwata; Mizuyo Takamatsu; Caren Tischendorf
Mathematics of Computation, 81, 278, 923, 939, 2012年04月, [査読有り]
英語, 研究論文(学術雑誌) - Learning Valuation Functions
Maria Florina Balcan; Florin Constantin; Satoru Iwata; Lei Wang
The Twenty-Fifth Conference on Learning Theory (COLT'12), 1, 24, 2012年, [査読有り] - Approximating Minimum Linear Ordering Problems
Satoru Iwata; Prasad Tetali; Pushkar Tripathi
The Fifteenth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the Sixteenth International Workshop on Randomization and Computation (APPROX-RANDOM'12), 206, 217, 2012年, [査読有り] - A Flow Model Based on Polylinking Systems
Michel X. Goemans; Satoru Iwata; Rico Zenklusen
Mathematical Programming, 135, 1, 23, 2012年, [査読有り] - A Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems
Toshinari Itoko; Satoru Iwata
Japan Journal of Industrial and Applied Mathematics, 29, 453, 468, 2012年, [査読有り] - On the Kronecker Canonical Form of Mixed Matrix Pencils
Satoru Iwata; Mizuyo Takamatsu
SIAM Journal on Matrix Analysis and Applications, 32, 1, 44, 71, 2011年, [査読有り]
英語, 研究論文(学術雑誌) - Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
Satoru Iwata; Mizuyo Takamatsu
Integer Programming and Combinatoral Optimization, IPCO 2011, 6655, 274, 286, 2011年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Index Characterization of Differential-Algebraic Equations in Hybrid Analysis for Circuit Simulation
Mizuyo Takamatsu; Satoru Iwata
International Journal of Circuit Theory and Applications, 38, 4, 419, 440, 2010年05月, [査読有り]
英語, 研究論文(学術雑誌) - An Algorithm for Minimum Cost Arc-Connectivity Orientations
Satoru Iwata; Yusuke Kobayashi
Algorithmica, 56, 4, 437, 447, 2010年04月, [査読有り]
英語, 研究論文(学術雑誌) - Minimum Average Cost Clustering
Kiyohito Nagano; Satoru Iwata; Yoshinobu Kawahara
Twenty-fourth Conference on Neural Information Processing Systems (NIPS'10), 1759, 1767, 2010年, [査読有り] - Index Minimization of Differential-Algebraic Equations in Hybrid Analysis for Circuit Simulation
Satoru Iwata; Mizuyo Takamatsu
Mathematical Programming, 121, 1, 105, 121, 2010年01月, [査読有り]
英語, 研究論文(学術雑誌) - Hybrid Analysis of Nonlinear Time-Varying Circuits Providing DAEs with Index at Most One
Satoru Iwata; Mizuyo Takamatsu; Caren Tischendorf
Scientific Computing in Electrical Engineering SCEE 2008, 14, 151, +, 2010年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - A Simple Combinatorial Algorithm for Submodular Function Minimization
Satoru Iwata; James B. Orlin
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09), 1230, 1237, 2009年, [査読有り] - Approximating Submodular Functions Everywhere
Michel X. Goemans; Nicholas J. A. Harvey; Satoru Iwata; Vahab Mirrokni
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09), 535, 544, 2009年, [査読有り] - Computing the Degrees of All Cofactors in Mixed Polynomial Matrices
Satoru Iwata; Mizuyo Takamatsu
SIAM Journal on Discrete Mathematics, 23, 2, 647, 660, 2009年, [査読有り]
英語, 研究論文(学術雑誌) - Submodular Function Minimization under Covering Constraints
Satoru Iwata; Kiyohito Nagano
Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS'09), 671, 680, 2009年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Recent Results on Well-Balanced Orientations
Attila Bernath; Satoru Iwata; Tamas Kiraly; Zoltan Kiraly; Zoltan Szigeti
Discrete Optimization, 5, 4, 663, 676, 2008年11月, [査読有り]
英語, 研究論文(学術雑誌) - Index Reduction for Differential-Algebraic Equations by Substitution Method
Mizuyo Takamatsu; Satoru Iwata
Linear Algebra and Its Applications, 429, 8-9, 2268, 2277, 2008年10月, [査読有り]
英語, 研究論文(学術雑誌) - Solving Linear Programs from Sign Patterns
Satoru Iwata; Naonori Kakimura
Mathematical Programming, 114, 2, 393, 418, 2008年08月, [査読有り]
英語, 研究論文(学術雑誌) - Finding Coherent Cyclic Orders in Strong Digraphs
Satoru Iwata; Takuro Matsuda
Combinatorica, 28, 83, 88, 2008年, [査読有り] - Submodular function minimization
Satoru Iwata
Mathematical Programming, Ser. B, 112, 45, 64, 2008年, [査読有り] - The Independent Even Factor Problem
Satoru Iwata; Kenjiro Takazawa
SIAM Journal on Discrete Mathematics, 22, 4, 1411, 1427, 2008年, [査読有り]
英語, 研究論文(学術雑誌) - Computing the Inertia From Sign Patterns
Naonori Kakimura; Satoru Iwata
Mathematical Programming, 110, 1, 229, 244, 2007年06月, [査読有り]
英語, 研究論文(学術雑誌) - Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems
Toshinari Itoko; Satoru Iwata
Proceedings of the Twelfth International Conference on Integer Programming and Combinatorial Optimization, 267, 279, 2007年, [査読有り] - Algorithm for Advanced Canonical Coding of Planar Chemical Structures That Considers Stereochemical and Symmetric Information
Shungo Koichi; Satoru Iwata; Takeaki Uno; Hiroyuki Koshino; Hiroko Satoh
Journal of Chemical Information and Modeling, 47, 1734, 1746, 2007年, [査読有り] - Combinatorial Analysis of Singular Matrix Pencils
Satoru Iwata, Ryo Shimizu
SIAM Journal on Matrix Analysis and Applications, 29, 245, 259, 2007年, [査読有り] - Linking Systems and Matroid Pencils
Satoru Iwata
Journal of the Operations Research Society of Japan, 50, 315, 324, 2007年, [査読有り] - The Independent Even Factor Problem
Satoru Iwata; Kenjiro Takazawa
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07), 1171, 1180, 2007年, [査読有り]
英語, 研究論文(国際会議プロシーディングス) - Bisubmodular Function Minimization
Satoru Fujishige; Satoru Iwata
SIAM Journal on Discrete Mathematics, 19, 1065, 1073, 2006年, [査読有り] - Computing the Inertia from Sign Patterns
Naonori Kakimura; Satoru Iwata
Proceedings of the Eleventh International Conference on Integer Programming and Combinatorial Optimization, 335, 348, 2005年, [査読有り] - Combinatorial Analysis of Generic Matrix Pencils
Satoru Iwata; Ryo Shimizu
Proceedings of the Eleventh International Conference on Integer Programming and Combinatorial Optimization, 246, 248, 2005年, [査読有り] - Effective Consideration of Ring Structures in CAST/CNMR for Highly Accurate 13C NMR Chemical Shift Prediction
Hiroko Satoh; Hiroyuki Koshino; Takeaki Uno; Shungo Koichi; Satoru Iwata; Tadashi Nakata
Tetrahedron, 61, 7431, 7437, 2005年, [査読有り] - Matroid Matching via Mixed Skew-Symmetric Matrices
James Geelen; Satoru Iwata
Combinatorica, 25, 187, 215, 2005年, [査読有り] - A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
SIAM Journal on Discrete Mathematics, 19, 304, 320, 2005年, [査読有り] - A Capacity Scaling Algorithm for M-Convex Submodular Flow
Satoru Iwata; Satoko Moriguchi; Kazuo Murota
Mathematical Programming, 103, 181, 202, 2005年, [査読有り] - A Capacity Scaling Algorithm for MConvex Submodular Flow
Satoru Iwata; Satoko Moriguchi; Kazuo Murota
Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, 352, 367, 2004年, [査読有り] - A network flow approach to cost allocation for rooted trees
Satoru Iwata; Nozomu Zuiki
Networks, 44, 297, 301, 2004年, [査読有り] - A Constrained Independent Set Problem for Matroids
Tamás Fleiner; Andras Frank; Satoru Iwata
Operations Research Letters, 32, 23, 26, 2004年, [査読有り] - Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
Satoru Iwata
Algorithmica, 36, 331, 341, 2003年, [査読有り] - The Linear Delta-Matroid Parity Problem
James F. Geelen; Satoru Iwata; Kazuo Murota
Journal of Combinatorial Theory, Series B, 88, 377, 398, 2003年, [査読有り] - Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
Combinatorica, 23, 503, 525, 2003年, [査読有り] - A push-relabel framework for submodular function minimization and applications to parametric optimization
Lisa Fleischer; Satoru Iwata
Discrete Applied Mathematics, 131, 2, 311, 322, 2003年, [査読有り] - A Faster Scaling Algorithm for Minimizing Submodular Functions
Satoru Iwata
SIAM Journal on Computing, 32, 4, 833, 840, 2003年, [査読有り] - A faster scaling algorithm for minimizing submodular functions
Satoru Iwata
Proceedings of the Ninth International Conference on Integer Programming and Combinatorial Optimization, 1, 8, 2002年, [査読有り] - A Fully Combinatorial Algorithm for Submodular Function Minimization
Satoru Iwata
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), 915, 919, 2002年, [査読有り] - On Matroid Intersection Adjacency
Satoru Iwata
Discrete Mathematics, 242, 277, 281, 2002年, [査読有り] - Locating Sources to Meet Flow Demands in Undirected Networks
Kouji Arata; Satoru Iwata; Kazuhisa Makino; Satoru Fujishige
Journal of Algorithms, 42, 54, 68, 2002年, [査読有り] - A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow
Lisa Fleischer; Satoru Iwata; S. Thomas McCormick
Mathematical Programming, 92, 119, 139, 2002年, [査読有り] - Conjugate Scaling Algorithm for Fenchel-type Duality in Discrete Convex Optimization
Satoru Iwata; Maiko Shigeno
SIAM Journal on Optimization, 13, 204, 211, 2002年, [査読有り] - A Fully Combinatorial Algorithm for Submodular Function Minimization
Satoru Iwata
Journal of Combinatorial Theory, Series B, 84, 2, 203, 212, 2002年, [査読有り] - A Descent Method for Submodular Function Minimization
Satoru Fujishige; Satoru Iwata
Mathematical Programming, 92, 387, 390, 2002年, [査読有り] - Bisubmodular Function Minimization
Satoru Fujishige; Satoru Iwata
Proceedings of the Eighth International Conference on Integer Programming and Combinatorial Optimization, 160, 169, 2001年, [査読有り] - Combinatorial Relaxation Algorithm for Mixed Polynomial Matrices
Satoru Iwata; Kazuo Murota
Mathematical Programming, 90, 353, 371, 2001年, [査読有り] - A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions
Satoru Iwata; Lisa Fleischer; Satoru Fujishige
Journal of the ACM, 48, 4, 761, 777, 2001年, [査読有り] - Improved Algorithms for Submodular Function Minimization and Submodular Flow
Lisa Fleischer; Satoru Iwata
Proceedings of the Thirty-Second ACM Symposium on Theory of Computing (STOC'00), 107, 116, 2000年, [査読有り] - A Combinatorial, Strongly Polynomial- Time Algorithm for Minimizing Submodular Functions
Satoru Iwata; Lisa Fleischer; Satoru Fujishige
Proceedings of the Thirty-Second ACM Symposium on Theory of Computing (STOC'00), 97, 106, 2000年, [査読有り] - Algorithms for Submodular Flows
Satoru Fujishige; Satoru Iwata
IEICE Transactions on Information and Systems, E83-D, 322, 329, 2000年, [査読有り] - Relaxed Most Negatived Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow
Maiko Shigeno; Satoru Iwata; S. Thomas McCormick
Mathematics of Operations Research, 25, 76, 104, 2000年, [査読有り] - A Fast Cost Scaling Algorithm for Submodular Flow
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
Information Processing Letters, 74, 123, 128, 2000年, [査読有り] - A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
Proceedings of the Seventh International Conference on Integer Programming and Combinatorial Optimization, 259, 272, 1999年, [査読有り] - Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
Satoru Iwata
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), 476, 483, 1999年, [査読有り] - Minimizing a Submodular Function Arising from a Concave Function
Satoru Fujishige; Satoru Iwata
Discrete Applied Mathematics, 92, 211, 215, 1999年, [査読有り] - A Faster Algorithm for Minimum Cost Submodular Flows
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98), 167, 174, 1998年, [査読有り] - Patterns that preserve sparsity in orthogonal factorization
Satoru Iwata; D.D. Olesky; P. van den Driessche
Linear Algebra and Its Applications, 268, 345, 354, 1998年, [査読有り] - Block-Triangularization of Skew-Symmetric Matrices
Satoru Iwata
Linear Algebra and Its Applications, 273, 215, 226, 1998年, [査読有り] - Fast Bipartite Network Flow Algorithms for Assembly and Scheduling
Satoru Iwata; Tomomi Matsui; S. Thomas McCormick
Operations Research Letters, 22, 137, 143, 1998年, [査読有り] - Structural Analysis of Fault-Tolerance for Homogeneous Systems
Reiko Tanaka; Satoru Iwata; Seiichi Shin
Transactions of the Society of Instrument and Control Engineers, 33, 441, 447, 1997年, [査読有り] - A Cost-Scaling Algorithm for 0-1 Submodular Flows
Maiko Shigeno; Satoru Iwata
Discrete Applied Mathematics, 73, 261, 273, 1997年, [査読有り] - A Capacity Scaling Algorithm for Convex Cost Submodular Flows
Satoru Iwata
Mathematical Programming, 76, 299, 308, 1997年, [査読有り] - A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
Satoru Iwata; Kazuo Murota; Maiko Shigeno
Mathematics of Operations Research, 22, 803, 813, 1997年, [査読有り] - Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders
Hiroshi Imai; Satoru Iwata; Kyoko Sekine; Kensyu Yoshida
Proceedings of the Second Annual Symposium on Computing and Combinatorics (COCOON), 68, 80, Springer Berlin Heidelberg, 1996年
論文集(書籍)内論文 - A Capacity Scaling Algorithm for Convex Cost Submodular Flows
Satoru Iwata
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96), 482, 489, 1996年, [査読有り] - Horizontal Principal Structure of Layered Mixed Matrices: Decomposition of Discrete Systems by Design-Variable Selections
Satoru Iwata; Kazuo Murota
SIAM Journal on Discrete Mathematics, 9, 71, 86, 1996年, [査読有り] - Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
Satoru Iwata; Kazuo Murota; Izumi Sakuta
SIAM Journal on Scientific Computing, 17, 993, 1012, 1996年, [査読有り] - A Theorem on the Principal Structure for Independent Matchings
Satoru Iwata; Kazuo Murota
Discrete Applied Mathematics, 61, 229, 244, 1995年, [査読有り] - Principal Structure of Submodular Systems and Hitchcock-type Independent Flows,
Satoru Iwata
Combinatorica, 15, 515, 532, 1995年, [査読有り] - A Minimax Theorem and a Dulmage-Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
Satoru Iwata; Kazuo Murota
SIAM Journal on Matrix Analysis and Applications, 16, 719, 734, 1995年, [査読有り] - A Dual Approximation Approach to Weighted Matroid Intersection
Maiko Shigeno; Satoru Iwata
Operations Research Letters, 18, 153, 156, 1995年, [査読有り] - Block-Triangularizations of Partitioned Matrices under Similarity/Equivalence Transformations
Hisashi Ito; Satoru Iwata; Kazuo Murota
SIAM Journal on Matrix Analysis and Applications, 15, 1226, 1255, 1994年, [査読有り] - H-infinity Optimal Control for Symmetric Linear Systems
Satoru Iwata
Japan Journal of Industrial and Applied Mathematics, 10, 97, 107, 1993年, [査読有り]
- RMapDB: chemical reaction route map data for quantum mechanical-based data chemistry.
H. Satoh; T. Oda; K. Nakakoji; T. Uno; S. Iwata; K. Ohno, Materials Cloud Archive, 2020.138, 2020年11月, [査読有り]
英語, その他 - 2本の2次制約付き非凸2次計画問題に対する多項式時間アルゴリズム
坂上 晋作; 中務 佑治; 武田 朗子; 岩田 覚, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015, 166, 167, 2015年03月26日
公益社団法人日本オペレーションズ・リサーチ学会, 日本語 - Wolfeの最小ノルム点アルゴリズムによるSVM学習 (情報論的学習理論と機械学習 情報論的学習理論ワークショップ)
北村昌士; 武田朗子; 岩田覚, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 114, 306, 65, 71, 2014年11月17日
本論文では,凸多面体上のノルム最小点を有限回の反復で厳密に計算するWolfeのアルゴリズムを,ヒンジロス付きSVMの学習に適用する.提案手法が,LIBSVM等の既存手法よりも速く動作することを数値実験によって示す.また,元の問題の変種問題を解くことで高速化を図ったLIBLINEARと比較しても,サンプル数が特徴数より十分多い時には,提案手法の方が高精度の判別器を高速に構成することを数値実験で確認する., 一般社団法人電子情報通信学会, 日本語 - 2-A-5 Wolfeの最小ノルム点アルゴリズムによるSVM学習
北村 昌士; 武田 朗子; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2014, 170, 171, 2014年08月28日
公益社団法人日本オペレーションズ・リサーチ学会, 日本語 - 電力網のサイバー攻撃に対する安全性評価 : ハイパーグラフ最小カット問題の応用
山口 勇太郎; 小川 安奈; 武田 朗子; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2014, 206, 207, 2014年08月28日
公益社団法人日本オペレーションズ・リサーチ学会, 日本語 - 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
土村 展之; 森口 聡子; 垣村 尚徳; 岩田 覚; 室田 一雄, 研究報告アルゴリズム(AL), 2011, 4, 1, 6, 2011年01月05日
マトロイド・劣モジュラ関数の研究の流れを汲んだ離散凸解析による統一的枠組みの中で,離散最適化問題を効率的に解く各種アルゴリズムが提案されてきた.離散凸解析理論の普及を目的として,これらの成果を応用分野の研究者・実務家が享受できるように,関連するアルゴリズムを紹介するデモンストレーションソフトウェアと,アプリケーションソフトウェアを開発した.ソルバ及びデモンストレーションソフトウェアの WEB 公開について報告する.In discrete convex analysis, which is a unified framework of discrete convex functions based on the theory of matroids and submodular functions, efficient discrete optimization algorithms were proposed. In order to disseminate these theoretical results in application fields, we release softwares and web applications implementing algorithms developed in discrete convex analysis., 情報処理学会, 日本語 - 1-B-6 線形計画問題の符号可解性
垣村 尚徳; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2005, 38, 39, 2005年09月14日
公益社団法人日本オペレーションズ・リサーチ学会, 日本語 - 符号対称行列のSylvester指数
垣村 尚徳; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2004, 228, 229, 2004年09月08日
公益社団法人日本オペレーションズ・リサーチ学会, 日本語 - Structural analysis of fault-tolerance for homogeneous systems
Reiko Tanaka; Satoru Iwata; Seiichi Shin, Proceedings of the IEEE Conference on Decision and Control, 2, 1920, 1921, 1996年
英語, 書評論文,書評,文献紹介等
- Matroid Parity
Satoru Iwata
The Twelfth Annual Meeting of the Asian Association for Algorithms and Computation (AAAC), 2019年
[招待講演] - Weighted Linear Matroid Parity
Satoru Iwata
The Twenty-Eighth International Symposium on Algorithms and Computation (ISAAC), 2017年
[招待講演] - Submodular Functions: Optimization and Approximation
Satoru Iwata
International Congress of Mathematicians (ICM), 2010年
[招待講演] - Submodular Function Minimization under Covering Constraints
Satoru Iwata; Kiyohito Nagano
The Sixth Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2009年
[招待講演] - Approximating Submodular Functions
Satoru Iwata
Lunteren Conference on Mathematics of Operations Research, 2009年01月
[招待講演] - Minimizing Submodular Functions
Satoru Iwata
Lunteren Conference on Mathematics of Operations Research, 2009年01月
[招待講演] - Submodular Functions
Satoru Iwata
ADONET-CIRM School on Graphs and Algorithms, 2007年10月
[招待講演] - Index Minimization of Differential-Algebraic Equations in Hybrid Analysis for Circuit Simulation
Satoru Iwata; Mizuyo Takamatsu
The Fifth Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2007年04月
[招待講演] - Submodular Function Minimization
Satoru Iwata
The Nineteenth International Symposium on Mathematical Programming, 2006年08月
[招待講演] - Submodular Function Minimization
Satoru Iwata
International Conference on High Performance Scientific Computing, 2006年03月
[招待講演] - Combinatorial Approaches to Matrix Pencils
Satoru Iwata
The Third Sino-Japanese Optimization Meeting, 2005年11月
[招待講演] - Linking Systems and Matroid Pencils
Satoru Iwata
The Fourth Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2005年06月
[招待講演]
- 化学反応の予測・設計・制御のための最適化手法の構築
戦略的創造研究推進事業
2024年10月 - 2030年03月
岩田 覚; 松岡 和; 大城 泰平
本研究課題は、量子化学計算と数理最適化を融合して、触媒や反応条件の最適設計を行う方法論の構築を目的としています。そのために、分子の電子効果・立体効果を近似するバーチャル分子モデルを導入します。さらに、触媒や反応条件の各パラメータ値が収率や選択性に及ぼす影響の偏導関数値を用いて最適パラメータ値を算出し、これを近似的に実現する分子や条件を選択することにより化学反応を最適化する方法論を確立します。
科学技術振興機構, CREST, 東京大学, JPMJCR24Q2 - 分子の3次元幾何構造に関する計算手法の開発と応用
科学研究費助成事業
2021年04月01日 - 2026年03月31日
佐藤 寛子; 岩田 覚
分子の立体的な構造は活性や物性を決める重要な要素の1つであり,近年のコンピュータ性能の向上によって高精度かつ大規模な3次元(3D)分子構造データの獲得と蓄積が可能となってきた。本研究では,データサイエンスの活発化と相まって今後さらに活発化すると期待される3D分子データ活用のための新技術の確立と実証を目指し,データ化学と離散情報学を融合させた効率的アルゴリズムを開発し,分子の3D幾何構造に関する応用研究を実施する。具体的には,我々が最近開発した汎用的3D分子類似度判定法G-RMSDを中心に新規アルゴリズムを開発し,分子設計や化学反応予測等における従来法では困難な問題の解決に挑戦する。
令和3年度は以下の3点について重点的に研究を実施した。
まず,G-RMSDを中心とした新規アルゴリズムの1つとして,分子間のRMSD最小値の最適解を保証する厳密解法を開発,実装した。2点目として,商用ソフトウェアMATLABで動くG-RMSDプログラムコードをフリーオープンソースコードOctaveに移植し,汎用性を向上させた。3点目として,分子動力学シミュレーションによる化学反応過程に存在する点としてサンプリングされる分子構造群を最もエネルギーの低い経路を辿る線で繋ぐ最安定経路を同定する新手法開発の基礎データとなる分子動力学シミュレーションを実施した。
日本学術振興会, 基盤研究(C), 大学共同利用機関法人情報・システム研究機構(機構本部施設等), 21K11776 - 新計算モデルにおけるアルゴリズム・最適化
科学研究費助成事業
2020年11月19日 - 2025年03月31日
河原林 健一; 岩田 覚; 吉田 悠一; 福永 拓郎; 平原 秀一; Avis David
現在の情報検索技術(GoogleのPageRank)、セキュリティ技術(Appleの(Local) Differential Privacy)などのアルゴリズム革新は国家規模のビジネス創成につながり、現在のGAFAを作り上げた。ここで重要なのは、PageRankもDifferential Privacyもアルゴリズムおよび理論計算機科学、離散数学の基礎・理論研究であり、最初から応用を志向した仕事ではない点である。このような事実をMicrosoft、IBM、Google、Yahoo、Facebook、Amazonなどの巨大 IT企業は創業当初から認識しており、現在でもアルゴリズム、離散数学に手厚いサポートをしている。
本研究では、このような背景を踏まえ、理論分野のさらなる強化、特にグラフアルゴリズム、計算量理論、組合せ最適化のそれぞれの分野での世界的な研究成果発信と学術変革を目指す。またこれらを通して研究領域内での「人材育成」および、コロナ期における世界的なアルゴリズム国際共同研究拠点構築を目指す。
日本学術振興会, 学術変革領域研究(A), 国立情報学研究所, 20H05965 - 前田化学反応創成知能プロジェクト
戦略的な研究開発の推進 戦略的創造研究推進事業 ERATO
2019年 - 2024年
前田 理; 岩田 覚
本プロジェクトでは、世界に先駆けて開発した反応経路自動探索技術(AFIR法)と、組合せ最適化技術を基盤とし、量子化学計算、情報科学、さらにはマテリアルズ・インフォマティクスの技術を統合することで、化学反応における「原子の動きの全貌」を予測し、有用な未知の化学反応を次々に提案する「化学反応創成知能」を創出します。 具体的には、AFIR法を用い、さまざまな反応物や触媒の組み合わせに対して「反応経路ネットワーク」を計算し、得られる反応経路データベースから目的物合成に適した化学反応を迅速に設計・提案するシステムを構築します。このとき、目的生成物の収率が最大となる反応物の組み合わせを導くために、組合せ最適化技術を活用します。また、反応経路ネットワークから反応性を支配する因子を抽出し、分子構造との相関を学習させることで、反応性を言い当てられる機械を創出します。 また、「化学反応創成知能」は実験的には検出できない超微量な副生物の存在まで明らかにできるため、そこから未知の化学反応が発見される期待もあります。さらに、合成ロボットへの「化学反応創成知能」の実装を試み、目的とする物質を生成するのに最適な化学反応を発見するスピードを大幅に加速することを目指します。
科学技術振興機構, 北海道大学 - 一般化固有値計算による大域最適化手法の展開
科学研究費助成事業 基盤研究(B)
2017年04月01日 - 2022年03月31日
岩田 覚; 武田 朗子; 中務 佑治
本研究課題では,一般に効率的なアルゴリズムの設計が原理的に不可能であると言われている非凸最適化問題の中でも幾何的な背景を有する問題に焦点を絞り,その構造を利用して,大域最適解を見出す効率的なアルゴリズムを設計する手法を確立することを目的とする.具体的には,一般化固有値計算を用いて,制約条件数が定数で抑えられる2次制約2次計画問題に対する実装可能な多項式時間厳密解法を開発することを目標とする.さらに,一般化固有値計算を利用した非凸最適化問題の解法を,できるだけ一般的な枠組みに拡張することを目指す.特に,重み付きプロクラステス解析への応用を試みる.
非線形関数の無制約最適化を中心に広く使わる信頼領域法では,反復毎に信頼領域と呼ばれる楕円体の中で,2次目的関数を最小化する問題を解く.この問題は,信頼領域部分問題 (TRS) と呼ばれ, 非凸最適化問題であるが,半正定値計画緩和が常に最適解を与えるために,多項式時間で解けることが知られている.代表者等が既に開発した一般化固有値問題を経由してTRSを解く手法は,半正定値計画緩和による従来の解法よりも格段に高速で,高い精度を達成している.一方,TRSに多数の線形不等式制約が付加された一般化TRSに対して,半正定値計画緩和による手法を中心に,多くの研究がなされている.特に,付加する不等式条件数が定数の場合には多項式時間が得られることが報告されている.
本年度は,1本の制約式のみを含む非凸2次制約2次計画問題(QCQP)に対して,一般化固有値問題に帰着することによって,高速に最適解を得る手法を論文で発表した.この手法は,信頼領域部分問題に対して以前に開発した高速解法の拡張に当たる.また,プロクラステス解析に関する考察を進めた.特に,一般化プロクラステス解析において,半正定値緩和が実用上有効であることの構造的な背景が明らかになった.
日本学術振興会, 基盤研究(B), 東京大学, 17H01699 - 一般化固有値計算による大域最適化手法
科学研究費助成事業 挑戦的萌芽研究
2014年04月01日 - 2017年03月31日
岩田 覚; 武田 朗子; 中務 佑治
本研究課題は,一般に効率的なアルゴリズムの設計が原理的に不可能であると言われている非凸最適化問題の中でも幾何的な背景を有する問題に焦点を絞り,その構造を利用して大域的最適解を効率的に見出すアルゴリズムを設計する手法を確立することを目的とした.特に,高次元空間中の2楕円体間の符号付き距離を次元の6乗に比例する程度の時間で計算するアルゴリズムを開発した.この手法を拡張して,一般化CDT問題に対しても同程度の計算時間で厳密解が計算できることを示した.また,信頼領域法の各反復で解かれる信頼領域部分問題が一般化固有値問題に帰着され,高速高精度に解けることを示した.
日本学術振興会, 挑戦的萌芽研究, 東京大学, 26540007 - 最適化技法との融合による計算限界解析法の深化
科学研究費助成事業
2012年06月28日 - 2017年03月31日
加藤 直樹; 岩田 覚; 岡本 吉央; 神山 直之; 来嶋 秀治; BELMONTE Remy
得られた成果は以下の通りである,
1. 近年活発に研究されている拡張定式化に関連して,理論上・応用上重要な疎性マトロイドに付随する多面体のコンパクトな表現を与えた.2. 行列表現を持つ線形マトロイドに対して,重み付きのマトロイド・パリティ問題を解く最初の多項式時間アルゴリズムを与えた.3. しらみつぶし探索法を本質的に改善できないと思われる問題間の新しい帰着 (困難性証明技法) を開発し,指数時間計算可能性の分野における新しい標準を築いた 4. #P困難性の知られる0-1ナップサック多面体の体積計算に対して,多項式時間決定性近似アルゴリズムを与えた.
日本学術振興会, 新学術領域研究(研究領域提案型), 24106005 - 劣モジュラ最適化の近似アルゴリズム
科学研究費助成事業 基盤研究(B)
2011年04月01日 - 2016年03月31日
岩田 覚; 髙澤 兼二郎; 谷川 眞一
劣モジュラ関数は,効率的に解くことのできる離散最適化問題に共通の構造して知られている.一方,実務上重要な多くの離散最適化問題はNP困難であり,現実的な時間内で近似解を得る近似アルゴリズムの設計が研究されてきた.本研究では,このような離散最適化の二つの大きな流れを融合して,汎用性の高い近似アルゴリズムを設計する手法を研究した.特に,劣モジュラ関数の一般化に当たるk劣モジュラ関数の最大化問題に対して,近似比1/2の近似アルゴリズムを設計した.さらに,単調k劣モジュラ関数に対しては,近似比がk/2(k-1)となる多項式時間アルゴリズムを開発した.
日本学術振興会, 基盤研究(B), 23300002 - 離散凸パラダイムによる最適化統一理論
科学研究費助成事業
2009年04月01日 - 2015年03月31日
室田 一雄; 田村 明久; 岩田 覚; 塩浦 昭義; 森口 聡子; 垣村 尚徳; 小林 佑輔; 土村 展之
工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」に よって統合する研究を行った.離散凸解析の理論と応用を, 連続・離散軸,凸・非凸軸,分野横断軸,の3つの観点から整理することによって,個々の数 理的技法や応用諸問題の相互関係を明確にし,数理の深化,応用の開拓,ソフト ウェアの整備の3つの観点から研究を行い,新たな展開を達成した.とくに,数理の深化については,L凸関数最小化アルゴリズムの詳細な解析やDC計画の枠組みの提示などの成果をあげた.
日本学術振興会, 基盤研究(B), 東京大学, 21360045 - ネットワーク構造解析アルゴリズムの開発とネットワークアルゴリズムの総合的展開
科学研究費助成事業
2010年 - 2012年
繁野 麻衣子; 山本 芳嗣; 吉瀬 章子; 八森 正泰; 岩田 覚
ネットワーク最適化に対する基礎理論を発展させ,ゲーム理論やグラフ理論と融合することで,社会システムにおけるネットワーク構造の分析を行った.具体的には,コミュニティ抽出のアルゴリズム構築と有効性の検証,情報伝播ネットワークの特徴付け,グラフの一様性を表す飽和グラフの分析などである.また,仮想計算機配置問題,オークションの財の割当,スタッフスケジューリング,タクシー配車問題などにネットワーク基礎理論が適用できることも示した.
日本学術振興会, 基盤研究(C), 筑波大学, 22510135 - 劣モジュラ的構造に基づく離散最適化基礎理論の展開と高速アルゴリズム開発
科学研究費助成事業
2008年 - 2012年
藤重 悟; 岩田 覚; 牧野 和久; 来嶋 秀治; 平井 広志
大規模離散最適化問題の有する劣モジュラ的な離散構造に注目し, 効率的なアルゴリズムの構築のために有効な離散構造を研究した.個別には,ネットワーク・フロー, マッチング,多品種フロー, 施設配置問題, 資源配分問題, グラフ連結度,通信網設計,待ち行列ネットワークに関わる離散構造,双対貪欲アルゴリズムに関わる離散構造(双対貪欲多面体, ゾノトープ) ,ホーン論理関数や安定マッチングの離散凸構造,などであり,個別の劣モジュラ的な離散構造の解明に基づき,それらの知見を横断的に総合する基礎理論の構築と高速アルゴリズムの開発を行った.
日本学術振興会, 基盤研究(B), 京都大学, 20310088 - 離散最適化技法による微分代数方程式モデルの指数減少法
科学研究費助成事業 基盤研究(C)
2008年 - 2010年
岩田 覚; 高松 瑞代
集積回路や化学プラントに代表される大規模動的システムは,微分演算子と代数方程式が混在した微分代数方程式(DAE)によって自然に記述される.しかし,微分代数方程式の数値解析においては,常微分方程式の場合と比較して,初期値の設定や安定性の保証が著しく困難となる.本研究課題では,回路の過渡現象をモデル化する微分代数方程式の導出において,数値的に最も解き易いものを効率的に見出す手法を開発した
日本学術振興会, 基盤研究(C), 京都大学, 20560057 - ネットワーク理論の基盤整備と伸張
科学研究費助成事業
2007年 - 2009年
繁野 麻衣子; 山本 芳嗣; 吉瀬 章子; 八森 正泰; 岩田 覚; 後藤 順哉
ネットワーク理論において横の広がりとなる基礎理論の構築と縦の広がりを作る実社会に適応したモデルの伸張を行い,基礎問題と拡張問題の両方に対して,アルゴリズム開発を行った.具体的には,修正可能性を考慮したネットワーク上の配置問題に対するアルゴリズム提案,通信ネットワークにおける耐故障性の指標開発,社会ネットワークにおけるコミュニティ抽出のハイパーグラフ上への拡張,グラフの向き付けに関する基本的性質やアルゴリズム開発などを行った.
日本学術振興会, 基盤研究(C), 筑波大学, 19510137 - 離散凸パラダイムの深化と拡大
科学研究費助成事業
2006年 - 2008年
室田 一雄; 田村 明久; 岩田 覚; 土村 展之; 森口 聡子; 塩浦 昭義
経済学,システム工学,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立し,それを広範囲の応用分野に浸透させる研究を行った.「離散凸パラダイム」の横糸を成す,構造定理やアルゴリズムを代表とする離散関数に関する数理の研究と,縦糸を成す,諸応用分野における具体的な諸問題に対する研究を行った.
日本学術振興会, 基盤研究(B), 東京大学, 18360048 - 離散最適化技法による行列束のロバスト数値計算とシステム解析への応用
科学研究費助成事業 若手研究(B)
2005年 - 2007年
岩田 覚
行列束のKronecker標準形は,微分代数方程式で記述される動的システムの解析において本質的な役割を果たしている.しかし,標準形の摂動に対する感度が非常に高く,計算誤差の発生しうる数値計算によって正確な標準形を得ることには困難を伴う.
本研究課題では,計算誤差が発生し得ない組合せ的計算を利用することによって数値計算の負担を減らして,できるだけ正確な標準形を安定に計算する手法を確立することを目的としている.従来の研究の結果,Kronecker標準形の構造指数のうち,冪零指数に関して,2部グラフ上の最大重みマッチングを利用した組合せ緩和法が確立されている.本研究課題は,組合せ緩和法に基づいて行指数・列指数を計算するアルゴリズムの設計と計算機上での実現を目的としている.
昨年度までの研究成果より,周期的な構造を有する2部グラフ上の最大マッチングを計算することによって,行指数・列指数の推定値が得られることが明らかとなった.
本年度は,引き続き,組合せ緩和法の設計に取り組み,世界標準的なソフトであるGUPTRIで採用されているアルゴリズムよりも効率的な新たなアルゴリズムを得た.しかし,計算精度に関しては,GUPTRIの方が優れているため,現時点では,組合せ的な推定値とGUPTRIとを併用するのが,最も適切な計算法であるとの結論に達した.
また,微分代数方程式の指数減少法への応用研究を行い,電気回路の数値解析手法として知られる混合解析の枠組みにおいて,最小指数を達成する微分代数方程式を導出する効率的なアルゴリズムを開発した.
日本学術振興会, 若手研究(B), 17760065 - 連続と離散の融合によるロバストアルゴリズム構築
科学研究費助成事業
2004年 - 2007年
杉原 厚吉; 室田 一雄; 今井 浩; 松井 知己; 岩田 覚; 大石 泰章
従来は連続計算の分野と離散計算の分野に分かれてそれぞれ独立になされてきたアルゴリズム研究の知見を融合し,両者の手法の長所を補完し合うことによって,諸計算のロバスト性を確保するための計算原理を開拓することが本研究の目的であった.本年度もこの目的に沿って研究を行い,次のような成果を得た.幾何計算の分野では,2次元および3次元の球ボロノイ図のロバストな計算法を開発した.これは,位相構造をいつも正しく判定できる高精度計算を用いるもので,必要な精度をもとの入力データの2d+4倍に置き換えることに成功した.また,流れの中でのボートの最短経路を求めるロバスト解法を高次元と曲面上とへ拡張した.さらに長方形詰込み問題の実用的解法を構成するとともに,一般の形の図形詰込み結果に基づいてハードメタルを切り取るためのカッターパス生成法を構成した.離散凸解析の分野では,定パリティジャンプシステム上のM凸関数が,合成積やグラフによる変換によってM凸性を保存することを示した.量子計算の分野では,カット凸多面体とベル不等式の関係を明らかにし,量子状態を記述するより強力な不等式を得た.サンプリングの分野では,マルコフ連鎖を用いたモンテカルロ法のためのパーフェクトサンプリング方法を開発した.組合せ最適化の分野では,数理計画問題の符号情報のみから最適解の性質を調べる方法を開発した.制御計算の分野では,制御対象パラメータのとり得る区間の中で常に安定性が保証されるロバスト制御法を,ロバスト線形不等式を条件とする半正定値問題に帰着させて解く方法を与えた.構造設計の分野では,不確定な外力に対する構造物の解析法を開発した.これらの諸成果を通じて,「連続計算における知見と離散計算における知見の交流によって,計算の安定化をはかることができる」というロバストな計算を確保するための一つの原理の有効性を確認することができた.
日本学術振興会, 特定領域研究, 東京大学, 16092204 - 離散凸パラダイムの確立
科学研究費助成事業
2003年 - 2005年
室田 一雄; 田村 明久; 岩田 覚; 土村 展之; 塩浦 昭義; 松浦 史郎
本研究課題の目的は,経済学,システム工学,オペレーションズ・リサーチ,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立することにある.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
(1)離散双対性に関わる最適化問題,とくに,M凸関数を目的関数に含む劣モジュラ流問題に対して,容量スケーリング手法に基づくアルゴリズムを提案した.一般のM凸劣モジュラ流問題に対して,このアルゴリズムはこれまでで最良の時間計算量をもつ.
(2)離散凸解析の枠組みとは独立に研究されてきたマルチモジュラー性という概念が,実質的にL凸性と等価な概念であることを示した.この結果をふまえ,整数格子点上で定義されたマルチモジュラー関数に対する離散分離定理などの諸性質を導いた.
(3)2次のM凸関数と木距離の間の密接な関係を示した.より具体的には,2次のM凸関数のヘッセ行列は実質的に木距離行列(にマイナスを掛けたもの)であることを証明した.
(4)整凸集合上の離散不動点定理を与えた.これは,数理経済学における一般均衡理論ならびに非協力ゲームへの応用をもつ.
(5)M凸関数の概念が,数理経済学で良く知られた粗代替性や単改良性と等価であることを明らかにした.
(6)離散凸解析の数理経済学への応用として,複数の不可分財と貨幣からなる市場において競争均衡が存在するための条件を与えるなどの理論構築を行うとともに,競争均衡を求めるアルゴリズムをM凸劣モジュラ流問題の枠組みを利用して開発した.
日本学術振興会, 基盤研究(B), 東京大学, 15360043 - 離散最適化技法による多変量解析
科学研究費助成事業 若手研究(B)
2002年 - 2004年
岩田 覚
本研究課題は,離散最適化の最新の成果を応用して,多変量データの新たな統計的解析手法を確立することを目的としている.多変量データの統計的解析に当たっては各変量を,相関行列に基づいて比較的少数のグループに分類することが重要なステップとなる.しかし,因子分析に代表される従来からの手法は,変量の線形結合を用いており,問題点が少なくない.本研究課題は,変量の線形結合を経由せずに,相関行列の半正定値対称性とその離散構造を積極的に利用した手法の開発を目的としている.
この目的を達成するために,最大対数尤度を基準として対称劣モジュラ関数最小化を用いる手法や,情報量規準の観点から最適な分割を局所近傍探索によって求める手法を開発し,計算機上で実現した.さらに,各種の人工データ及び実データに適用して,計算時間や分割精度の観点から手法の比較検討を行った.最大対数尤度を基準とする方法は,効率的な厳密解法を用いることができるという利点の反面,クラスタリングの鎖効果と呼ばれる現象が頻繁におこるという致命的な欠点があることが明らかになった.一方,AICやBICなどの情報量規準の最適化は,効率的な厳密解法を得ることが難しく,局所近傍探索を用いた手法を設計せざるを得ない.しかし,計算機実験の結果,多くのテストデータに対して,合理的な分割を安定して提示することが確認され,実際上有望な手法であるとの結論を得た.
日本学術振興会, 若手研究(B), 東京大学, 14750047 - 一般アクセス構造に対する秘密分散法の情報理論的性能解析と応用に関する研究
科学研究費助成事業
2003年 - 2003年
山本 博資; 小川 朋宏; 岩田 覚
本研究では,より一般的な秘密分散法(SSS)を構成する手法を与えると共に,その理論的評価を行っている.本年度は下記のような成果を得た.
(A)一般アクセス構造を(k,n)しきい値SSSを用いて実現する複数割当写像(multiple assignment mapping)に対して,最適な複数割当写像を整数計画を用いて構成する新たな方式を提案した.提案方式は,完全なアクセス構造だけでなく,ランプ型のアクセス構造やアクセス構造が一部未定である不完備なアクセス構造に対しても適用することができ,従来の割当法に比べてかなり効率'のよいSSSを実現できる.
(B)線形演算を用いた関数秘密分散法(SFSS)の構成法の提案,その理論的性能評価SFSSのl-out-of-l紛失通信への応用に関する研究成果を国際シンポジウム(IEEE-ISIT2003)で発表した.
(C)白黒・カラー・濃淡画像などからなる複数の秘密画像を一度に符号化できる視覚復号型秘密分散法(VSSS)の一般的な構成法に関する研究成果を,学術論文誌(IEICE)および国際シンポジウム(IEEE-ISIT2003)で発表した.
(D)(k,n)しきい値量子秘密分散法(QSSS)に対する符号化効率の評価を,Holeve相互情報量を用いて行った.これは,Nascimentらがコヒーレント情報量および参照系を用いて行った評価の別証明を与えたものである.さらに,(k,L,n)しきい値ランプ型QSSSを定義し,その符号化効率を評価すると共に,それが(k,n)しきい値QSSSよりもL倍効率がよくなることを証明した.
日本学術振興会, 特定領域研究, 東京大学, 15017227 - 低密度パリティ検査符号の有歪み圧縮への応用に関する研究
科学研究費助成事業
2002年 - 2003年
山本 博資; 小川 朋宏; 岩田 覚
低密度パリティ検査符号(LDPC符号)は、1962年Gallagerにより提案された誤り訂正符号であるが、最近の計算機パワーの急激な増加により、BP(Belief Propagation)アルゴリズムなどの繰り返し復号法が適用可能となり、高性能な誤り訂正能力を実現できるようになっている。これに対し、本研究そはLDPC符号を、誤り訂正ではなく、有歪みデータ圧縮符号化に利用すことを考え、その性能評価を行った。
14年度は、低密度パリティ検査符号を用いて有歪み圧縮を行うための符号化アルゴリズムを与え、さらに、LDPC符号に対するMac Kayのランダムアンサンブルにおいて、符号語長が大きくなるに連れて漸近的に圧縮限界であるレート歪み関数を達成するLDPC符号が存在するという符号化定理の証明手法を考案した。15年度は、その証明における暖昧な部分を修正し、完全な証明を与えると共に、その結果を英文論文としてまとめ、学術論文誌(IEEE Transactions on Information Theory)に発表した。その符号化定理では、符号長nに対して、パリテイ検査行列の列ハミング重みtがt=O(log n)のとき、nと共に漸近的にレート歪み関数が達成でき、t=O(n)のときは、nと共に指数関数的にレート歪み関数に収束することを証明している。
さらに、シミュレーションにより、有歪み圧縮の場合は、BPアルゴリズムをLDPC符号にそのまま適用するのでは、レート歪み関数をうまく実現できないことも示した。
日本学術振興会, 基盤研究(C), 東京大学, 14550347 - 秘密関数分散法に対する情報理論的性能評価と応用に関する研究
科学研究費助成事業
2002年 - 2002年
山本 博資; 小川 朋宏; 岩田 覚
本研究では,従来の秘密分散法を拡張した秘密関数分散法を始めとして,視覚復号型秘密分散法,量子秘密分散法,離散数学的手法を用いた秘密分散法などの新しい秘密分散法を取り上げ,それらの効率のよい構成法の開発およびその応用に関する研究を行っている.
本年度は,下記のような成果を得た.
A)秘密関数分散法に関して
(1)昨年度与えた秘密関数分散法の定義が分かりにくかったため,よりシンプルな定義と表記を与え,その定義に基づき,秘密関数分散法の符号化レートの下限を与えると共に,その下限を達成する線形な符号化法を与えた.
(2)ランプ型秘密関数分散法に関しても,(1)と同様の成果を得た.
(3)秘密関数分散法とグループ化秘密分散法とを組合わせることにより,結託に対してロバストな紛失通信システムを構築できることを示した.
(B)視覚復号型秘密分散法に関して
(1)濃淡画像に対する視覚復号型秘密分散法(VSSS)が,行列の多項式表現と偏微分方程式を利用して構成できることを示すと共に,その構成方法で,最適な(n,n)しきい値VSSSを構成できることを示した.これらの成果をまとめて,学術論文に発表した.
(2)複数の秘密画像を有するVSSSを考え,その秘密画像がカラー画像,白黒濃淡画像のどのような画像の場合でも,VSSSを構成できる手法を開発した.
(C)量子秘密分散法および離散的手法の秘密分散法への応用について検討を行った.
日本学術振興会, 特定領域研究, 東京大学, 14019028 - 秘密関数分散法に対する情報理論的性能評価と応用に関する研究
科学研究費助成事業
2001年 - 2001年
山本 博資; 小川 朋宏; 岩田 覚
本年度は,秘密関数分散法およびその他の秘密分散法に関して下記の成果を得た.
1.秘密関数分散法(Secret Function Sharing Scheme)に対する成果
(1)秘密関数分散法のセキュリティ条件をエントロピーを用いて定式化するとともに,秘密関数分散法における符号化レートの下限を情報理論的に導出した.
(2)Naorらの2変数関数を用いた秘密関数分散法を,線形演算を用いる方式に一般化する共に,上記の下限を達成する方式を示した.
(3)ランプ型の秘密関数分散法を提案するとともに,その性能を情報理論的に評価した.その結果,幅Lのランプ型秘密関数分散法を用いると,符号化効率がL倍改善されることを明らかにした.
(4)Koyamaの複数グループ間の秘密分散法を秘密関数分散法に導入するとともに,その応用として新しいランプ型の紛失通信プロトコルが作れることを明らかにした.
2.その他の秘密分散法に対する成果
(1)グレースケールの視覚復号型秘密分散法を,行列の多項式表現と偏微分方程式を利用した方式で構成できることを示した.また,(n, n)しきい値法の場合,その方法で画素拡大率が最も少ない最適なものが構成法できることを明らかにした.
(2)分散画像の組合わせ方で異なるカラー画像を復号できる,新しい視覚復号型秘密分散法の構成法を提案し,その理論解析を行った.
(3)量子秘密分散法や,一般の秘密分散法への離散最適化手法の応用などについて,調査を行った.
日本学術振興会, 特定領域研究(C), 東京大学, 13224028 - 離散最適化アルゴリズムの計算効率と離散構造
科学研究費助成事業
1998年 - 2000年
藤重 悟; 繁野 麻衣子; 牧野 和久; 岩田 覚; 高畑 貴志
本研究では,比較的容易に解ける問題の組合せ的構造を詳細に吟味し,それらの構造の本質を明らかにするとともに,効率的なアルゴリズムを設計するための統一的な指針を与えることを目的とした.主要な成果は以下の通りである.
本研究の第1の成果は,劣モジュラ関数最小化に関する長年の未解決問題であった組合せ的な強多項式時間アルゴリズムの構成に成功したことである.この結果は,離散最適化分野に大きなインパクトを与えた.さらに,この成果に続いて,劣モジュラ関数最小化に関する完全に組合せ的な強多項式時間アルゴリズムの開発,ならびに,劣モジュラ関数の一般化である双劣モジュラ関数最小化の組合せ的多項式時間アルゴリズムの開発を行った.
第2の成果は,ネットワーク上の最適化問題に関する研究である,流量条件をみたす施設配置問題を考察し,高速なアルゴリズムを開発した.また,最小カット問題のL_∞-ミニマックス型逆最適化問題の(パラメトリック手法を用いた)高速アルゴリズムの開発,ならびに,一般化フローに関連する複基多面体の特徴付けに成功した.
第3の成果として,分散システムにおいて用いられるコテリのなかで,最適コテリを求める多項式時間アルゴリズムの開発,ならびに,データ発掘,学習理論の分野で現れるハイパーグラフの部分横断列挙問題,多重横断列挙問題の擬多項式時間アルゴリズムの開発に成功した.
その他の主要な成果としては,不可分財のあるマッチング(均衡)モデルにおける粗代替条件が,それに関係する集合関数がM^*-凹関数であることと等価であることを示し,経済均衡解析と劣モジュラ性との深い関わりを明らかにした.
日本学術振興会, 特定領域研究(B), 大阪大学, 10205217 - 2分決定グラフ新構成法に基づく離散システム論と大規模最適化法の新展開
科学研究費助成事業
1997年 - 2000年
今井 浩; 岩田 覚; 稲葉 真理; 浅井 健一
本研究では,2分決定グラフ(BDD)に基づいた離散システム論に対する統一的アプローチを確立することと,プロトタイプシステムを統合システムへと発展させることを目指した.これによって,従来は不可能であった離散システムの構造全体の暗黙的・効率的表現をコンピュータ上に行なうことが可能になり,新たな展開が種々可能となった.本アプローチをネットワーク信頼性解析・結び目のJones多項式計算への展開し,実際に計算システムを開発した.計算量的には#P完全で難しいとされている問題でも,構造を活用して中規模な問題を解けることを実証した.たとえば,14×14の格子状のグラフのネットワーク信頼性関数を計算することが可能となった.また,Jones多項式計算の結果により,BDDアプローチの計算位相幾何学への発展も開けた.BDDの基礎理論においても,単調論理関数とその主項のBDDのサイズに関して理論的解析を行い,指数ギャップを証明した.
代数的なアプローチとの関係では,Grobner基底に代表される計算代数の離散システムへの適用についても新展開を図った.本研究では,整数計画の効率よく解けるネットワークフローの場合にこのアプローチを適用し,理論的解析がかなりのところまで進められることを示した.さらに,2分決定グラフが分岐プログラムの特殊な場合であることに着目し,計算モデルとしてのパワーを新コンピューティングモデルである量子計算に発展させる研究でも成果をあげた.具体的には,量子計算においてJones多項式との関係について検討し,さらにBDDのレベルにおいて,量子と現在の計算モデルとの間の計算能力差を示すことにも成功し,これについては発表を予定している.
日本学術振興会, 基盤研究(B), 東京大学, 09480050 - 組合せ最適化技法による代数計算とシステム解析への応用
科学研究費助成事業 奨励研究(A)
1998年 - 1999年
岩田 覚
動的システムの解析や設計に重要な役割を果たす多項式行列の小行列式の最大次数を求める算法設計の新しい方法論として、代数的手法と組会せ的手法を融合した。『組合せ緩和法』が提唱されている。本研究では、組合せ緩和法の枠組みを尊重しつつ、多項式行列の変形に多くの記憶領域を要するという問題点を克服するために、動的システムの解析や設計に本質的な行列ペンシルに対象を限定した上で、定数行列による行列変換のみを用いた新しい組合せ緩和算法を開発した。この成果を、99年1月にボルチモアで開かれた第10回ACM/SIAM離散アルゴリズム会議で発表した。
行列ペンシルの小行列式の最大次数は、Kronecker標準形の構造指数と密接な関係がある。行列のKronecker標準形を求めるアルゴリズムとしては、従来、反復法を中心とした研究が行われてきたが、本研究を通じて、消去法を基礎とした直接法によって構造指数を求められることが明らかとなった。
組合せ緩和法は、優れて斬新な方法論であるが、未だ実用的なレベルに達してはいない。その原因としては、算法の正当性を理解するために、数値計算の専門家やシステムの解析や設計に携わる技術者に馴染みの薄い、組合せ最適化のかなり高度な議論を必要としていることが挙げられる。この問題点は、使い勝手のよい信頼できるソフトウェアを提供することによって解消されるであろう。
また、行列の組合せ論的な側面を抽象化したマトロイドと不可分の関係にある劣モジュラ関数に関して、多項式時間で最小値を求める組合せ的なアルゴリズムを開発した。
日本学術振興会, 奨励研究(A), 大阪大学, 10750053 - 付値マトロイドによるシステム解析手法の研究
科学研究費助成事業
1997年 - 1999年
室田 一雄; 杉原 正顯; 降旗 大介; 岡本 久; 岩田 覚
付値マトロイドの概念を用いて工学システムの組合せ構造を扱う手法を研究することが本研究課題の目的である.以下の結果を得た.
(1)混合行列の数学的成果をシステムの構造解析の道具として利用できるように,組合せ論的正準形(CCF)の構成アルゴリズムを実際的観点から改良した.それをソフトウェアの形にしてインターネット上に公開した.
(2)付値マトロイドの双対定理は,混合多項式行列に適用した場合,変数と方程式を適当な階数微分することによってある種の標準形(よい性質をもつプロパー行列)に移せることを述べている.本研究では,付値マトロイドの双対定理に関連するアルゴリズムを多項式行列の場合に特殊化したものの詳細を検討した.
(3)マトロイドのパリティ問題と電気回路理論におけるRCG回路の可解性問題との関係について,混合歪対称行列の枠組みを呈示し,線形デルタマトロイドに関する双対定理との関係を示した.さらに,その立場からRCG回路の可解性問題の現状を整理して,既存のアルゴリズムより少ない手間で可解性を判定するアルゴリズムを示した.
(4)群論的対称性を有する分散制御システムの可制御性を,対称性のみに由来する組合せ構造に着目して論じた.群表現論の枠組みを用いて問題を定式化し,マトロイドの双対定理を利用することによって,システムが可制御性を保持するために必要な入力数の下限値を導出した.
日本学術振興会, 基盤研究(B), 京都大学, 09450042 - 科学計算における高速ソルバーの研究・開発
科学研究費助成事業
1997年 - 1998年
岡本 久; 佐々木 文夫; 高野 真一郎; 杉原 正顕; 森 正武; 室田 一雄; 磯 祐介; 西田 孝明; 岩田 覚; 大木谷 耕司
流体力学における高速算法(岡本、坂上、大木谷、西田)、建築構造解析における薄層要素法(高野)、ウェーブレット(佐々木)、保存型差分法の開発(降旗)等の研究を行った.岡本は代用電荷法の様々な応用についてサーベイした論文を発表した。また、岡本の指導によって京都大学大学院生小林健太が、極小曲面の簡便な作成プログラム開発に成功した。佐々木は直交ウェーブレット変換での積分核の違いによる、関数近似に関する研究を行い、従来、ウエーブレットとしては局在性が良くないためにあまり利用されていないマザーウェーブレットが、非常に良い近似を与えることを発見した.混合行列が物理的に自然な変換群の下で一意的に確定する正準形(Combinatorial Canonical Formと呼ばれる)をもつことが知られているが,室田と岩田はそのためのプログラムをMathematicaで開発し,インターネット上に公開した.杉原は代用電荷法の3次元ポテンシャル問題への適用に取り組み、球領域の場合において新しい点配置を考案し、その有効性を実験によって示した。その理論的研究にはまだ不明な点も多いが、今後の研究によってすこしづつ明らかになってくるであろう。また杉原は、2重指数関数型変数変換をSinc関数近似に適用し、そのアルゴリズムの誤差が最適であることを理論的に示した。磯は逆散乱問題の数値解析という困難な問題に挑戦し、多倍長計算を駆使して実用に耐える数値実験が可能であることを示した。池田は反応拡散系や流体問題の並列計算に取り組み、これまで理論的にあやふやであった点を理論的に改善した。
日本学術振興会, 基盤研究(B), 京都大学, 09554003 - 離散凸解析の研究
科学研究費助成事業
1997年 - 1997年
室田 一雄; 降旗 大介; 岩田 覚
マトロイドの公理を拡張することにより,整数格子点上で定義された整数値をとる関数に対して離散凸関数とでも呼ぶべき概念が得られることが,本研究の開始時に明らかになっていた.連続世界の凸解析におけるルジャンドル変換の離散版を導入することによって,整数格子点上で定義された整数値関数に対して共役関数の概念が定義され,これによって,離散凸関数はM凸性,L凸性といういわば表と裏(数理計画の用語ではprimalとdual)の姿をもつ,M凸性は交換公理の拡張により,また,L凸性は劣モジュラ性の拡張により特徴付けられる.本研究では,以下の結果を得た.
1.L凸集合の多面体的な特徴付けを与えた.とくに,L凸集合が三角不等式を満たす距離関数と同等であることを示した.これは,M凸集合が劣モジュラ不等式を満たす集合関数と同等であるという(既知の)事実に対応する結果である.
M凸関数の実効定義域は基多面体であるが,これを,一般化ポリマトロイドの場合に定式化し直したものはM^〓凸関数と呼ばれる(M凸関数の射影がM^〓凸関数である).これに共役な操作(制限)をL凸関数に施したものをL^〓凸関数と名付け,その性質を調べた.これによって,従来の関連研究との関係が明らかとなった.とくに,L^〓凸関数がFavati-Tardellaによる整凸関数に一致すること,離散中点凸性により特徴付けられることを示した.
3.M凸関数,L凸関数に関する離散双対定理の原証明は,M凸関数に対して構成的に最適双対変数を与え,L凸関数に対してはその共役をとるという形であった.本研究では,M凸関数とL凸関数に関して,独立に多面体的な別証明を見いだした.その結果,整多面体と離散凸関数の関係が明確になった.
日本学術振興会, 萌芽的研究, 京都大学, 09874046 - 数理計画法における離散凸性の研究
科学研究費助成事業
1996年 - 1996年
室田 一雄; 岩田 覚
1.付値マトロイドの公理を拡張することにより,整数格子点上で定義され整数値をとる関数に対して,離散凸関数とでも呼ぶべき概念が得られることが,本研究の開始時に明らかになっていたが,連続世界の凸解析におけるルジャンドル変換の離散版を導入することによって,整数格子点上で定義された整数値関数に対して共役関数の概念を導入した.これによって,離散凸関数は,いわば表と裏(数理計画の用語では,primalとdual)の姿をもつことになった.離散凸関数の表の姿をM凸性,裏の姿をL凸性と名付け,M凸性を交換公理を拡張することにより特徴付け,L凸性を劣モジュラ性を拡張することにより特徴付けた.
2.M凸関数の実効定義域は基多面体であるが,これを,一般化ポリマトロイドの場合に定式化し直した.基多面体と一般化ポリマトロイドは,ある意味で等価な概念であることは知られている事実であるから,これは一種の翻訳作業ということになるが,これによって,Camerini-Conforti-NaddefやFavati-Tardellaなどによる従来の関連研究との関係が明らかとなった.
3.離散凸関数の最小化のアルゴリズムについて,ある程度の進展があった.L凸関数がFavati-Tardellaの考察した関数の族に含まれることが分かり,彼らのアルゴリズムによってL凸関数が最小化できる.ただし,これは楕円体法を基礎としているので,純粋に組合せ的とは言い難いアルゴリズムである.一方,M凸関数の最小化については,その性質を巧みに使った組合せ的なアルゴリズムを開発できた.このアルゴリズムの計算量や有効性については、今後,直ちに調べる予定である.
日本学術振興会, 基盤研究(C), 京都大学, 08650078 - マトロイド・マッチングの構造理論とその回路網解析への応用
科学研究費助成事業 奨励研究(A)
1996年 - 1996年
岩田 覚
線型マトロイド・マッチングは,ジャイレータ抵抗回路網の構造可解性判定に応用されている.しかし,実際問題としては,構造的に可解であることを保証するばかりでなく,数値誤差の影響を受けない組合せ的な情報に基づいて,数値計算の合理的な解法手順を示すことが望まれる.
本研究では,線型マトロイド・マッチングの分解原理を確立し,分解を求める効率的な算法を与えることによって,この問題を解決した.
さらに,海外との共同研究によって,線型マトロイド・マッチングの一般化である線型デルタマトロイド・パリティ問題に関する最大最小定理と効率的な多項式時間算法を導いた.その結果,線型マトロイド・マッチング問題が効率的に解ける仕組みについても理解が深まった.
日本学術振興会, 奨励研究(A), 京都大学, 08750083 - 分岐の数値解析における精度保証の研究
科学研究費助成事業
1995年 - 1995年
室田 一雄; 岩田 覚; 岡本 久
1.分岐現象の多くは系の対称性に由来するので,群対称性をもつ方程式系の数値計算に関して,構造工学や制御工学における現状を調査,整理した.偏微分方程式の対称性を保持しながら離散化を行うことの重要性は,理論的・概念的レベルでは十分認識されているものの,具体的な計算技法としては確立されてはいない.ブロック対角化に基づく効率化の手法については,群論としての数学的な原理の部分は,多くの文献に明確に記述されているが,それを実際に適用した例は少ない.とくに,変換行列の生成や,行列の疎性との関わりについては,まだまだ,研究が少ない.後者に関して,疎行列手法の多くと群対称性に基づく分割手法は基本的に両立しうるとの結論を得た.
2.2次元流体の渦層の形成に関する数値計算を通じて,数値計算誤差が分岐解に与える影響の大きさを観察した.誤差の影響は大きく,これをうまくコントロールするような算法を用いることではじめて意味のある現象が再現される.現状では,算法の誤差を定性的に見積る段階に留まっており,精度保証の段階には至っていない.
3.材料の強度変動の仕組みを初期不整を伴う定常分岐によって説明しようとする研究(研究発表の項の池田らとの共著論文)の成果を逆手にとって数値計算に利用するという着想に至った.すなわち,数値計算上の丸め誤差を「初期不整」に,分岐の数値計算結果を「材料の強度」に対応させることにより,真の分岐解のより高精度の推定値が得られると期待される.この方法を発展させて精度保証法が構成できるかどうかは,今後の課題として残された.
日本学術振興会, 一般研究(C), 京都大学, 07650077 - 非線形特異摂動現象の数学解析と数値計算
科学研究費助成事業
1995年 - 1995年
岡本 久; 谷口 雅治; 岩田 覚; 竹井 義次; 室田 一雄; 河合 隆裕
特異摂動理論のNavier-Stokes方程式への応用に関し、岡本久は同方程式の新しい厳密解を発見し,その流体力学的な性質を解明した.そのひとつは,TamadaとDorrepaalによる「斜めにぶつかる淀み点流」の3次元版であり,もうひとつはLerayによる相似解のスキームの解の発見である.
流体の数値シミュレーションに関しては,渦法による数値実験を岡本久が行った.せん断流と渦層の相互作用,あるいは2枚の渦層の相互作用による複雑な運動,特に特異点の発生とその構造に関して,これまで漠然と想像されてきたこととは違うメカニズムが存在することがわかった.
河合隆裕と竹井義次は代数解析の手法を用いて特異摂動理論を研究し,パンルベ方程式との興味る関係を導いた.
室田一雄と岩田覚は数値線形代数理論の研究を通じて本研究に貢献した.特異摂動問題を離散化すると条件数の大きな行列あるいは独特の構造を持つ行列が現れる.こういった行列に関する連立方程式の解法には離散数学の手法が役に立つ.室田は精度の改良や高速化に関する多くの方法を提唱し,その有用性をしめした.
谷口雅治は反応拡散方程式系において特異摂動状態にある定常解の安定性を論じた.これまで知られていた「解の存在証明法」を大幅に改良し,すっきりした理論体系を構築した.また2次元遷移層の安定性を特異摂動理論の枠組で厳密に取り扱うことが可能であることを示し,そのスケーリング指数を決定することに成功した.
日本学術振興会, 一般研究(B), 京都大学, 07454032 - 離散システムの分解手法の通信網管理への応用
科学研究費助成事業 奨励研究(A)
1995年 - 1995年
岩田 覚
本研究は,大規模な通信網の管理のために実際問題として解くことが要求されるが,効率的な解法は望めないような最適化問題に対して,近似解や下界値といった有用な情報を得るために,劣モジュラ関数や基本分割に関する理論的な成果を活用する手法の開発を目的としていた.特に,交換機等の設備の更改に関する投資計画に関連して,交換機とその利用者との関係についての膨大なデータの構造を的確に把握するために,基本分割を利用した手法を開発した.この手法を計算機上で実現し,実際的なデータによってその有用性を実験的に確認した.
また,離散システムの分解手法そのものに関しては,基本構造と基本分割との間の関係に,マトロイドにおける強射の劣モジュラシステムへの拡張が重要な役割を果たしていることが明らかになった.さらに,劣モジュラシステムの強射系列に関する算法の高速化に成功した.
日本学術振興会, 奨励研究(A), 京都大学, 07750084 - 計算幾何学アルゴリズムに関する共同研究
科学研究費助成事業
1994年 - 1995年
今井 浩; 浅井 健一; 岩田 覚; 土谷 隆; 稲垣 宏; 今井 桂子; 浅野 孝夫; 杉原 厚吉; EDELSBRUNNER エルベルト; RAPPAPORT Da; TOUSSAINT Go; AVIS David; HELBERT Edel; DAVID Rappap; GODFRIED Tou; DAVID Avis
本科学研究費により平成6,7年度に渡って実施した国際共同研究について,その成果を報告する.この研究の中心テーマである計算幾何学は,幾何構造を有する図形などの情報処理問題を高速に解くアルゴリズムを,情報科学・情報工学でのアルゴリズム設計の立場から統一的に研究する分野である。これまでに,平面図形・空間図形に関係する問題を中心に,既存手法では解けなかったような大規模な問題を実用的時間内で解いたり,新たに生じてきた問題に対する新アルゴリスムを提供したりなどの有用な成果を上げてきた.本研究グループは,ここ十数年に渡って個々の研究者がそれぞれの国を訪問し,数カ月滞在するなどして共同研究を行ない,かなりの成果を上げてきた.しかし,個々の研究者での交流が主であり,グループ全体での研究会などの開催などは,国際会議などの前後の極く短期間の研究集会だけであり,個々の研究レベルの高さを,国際的な共同研究環境整備ができておらず,生かしきれていなかった面があった.それを本研究により,統合されたことによる成果を上げ,融合による新展開を図ることができた.
具体的には,本科学研究では,グループの各分担者の研究成果が,普遍的な基礎分野での成果から応用に直結した大規模プログラムまで広範囲に渡ることに基づき,それらを融合させて,計算幾何学のみならず情報科学・工学の基礎理論での新展開を図ることを目標に国際共同研究を行なった.具体的成果としては,計算幾何ワークベンチ,特に3角形分割などの基本的幾何構造に関するパッケージ開発ができ,理論的にも本科学研究費の共同研究により一定期間に渡っての共同討議を行ない,今後に続く研究成果が得られた.具体的成果については,論文リストを参照されたい.特に,3角形分割のパッケージは,関連分野に関する北米で最も大きな会議のACM計算幾何会議において,論文発表を2件と,さらにビデオによるデモンストレーションを行なう予定である.このプロジェクトの大元は,カナダ側代表のAvis教授による逆探索と呼ばれるアイデアで,これを本科学研究を通じて日本側の最適化技法と融合させ,新展開を図ることができた.頑健な幾何計算などでも当初の目標通りの成果を上げることができた.また、本共同研究により,日本とカナダ・アメリカの研究交流を通じて,情報科学・情報工学の分野における日本での研究の特徴を生かした貢献を示せた.
さらに,本共同研究を通して,D.Avis,D.Rappaport,H.Edelsbrunner教授との東京での共同研究が実現し,また日本側からは研究分担者として初年度に稲垣宏講師,岩田覚助手,また研究協力者の稲葉真理,小野剛氏が,さらに最終年度では浅野孝夫教授,浅井健一助手の北米訪問が実現され,McGill大学を中心に共同研究・討議を行なった.また,北米側のグループの来日については,共同研究の立場から海外旅費は全て向う持ちで,日本側からは一部の場合に国内滞在費を支出するにとどめた.さらに、カナダ側のグループの共同研究者であるJ.M.Robert,H.Everett副教授,さらにはH.Edelsbrunner教授が短期滞在した経験のあるアジア香港からS.-W.Cheng,M.Golin副教授らの来日へと交流が発展し,計算幾何のテーマに絞った共同研究会を開催することもできた.このように,本研究ではグループ内での大きな成果を着実に上げることはもとより,より広くアジア・環太平洋地域の研究者まで含めた交流を可能にし,国際研究協力の実を上げた.本研究の成果は既に日本語の教科書としても発表され,また開発されたパッケージについては,まずは国際会議で発表の後,インターネットなどを通じて,広く公開していく予定である.
日本学術振興会, 国際学術研究, 東京大学, 06044058 - 組合せ理論と群表現論に基づく大規模システムの構造解析手法の研究
科学研究費助成事業
1994年 - 1994年
岡本 久; 岩田 覚
1.大規模方程式系に関するマトロイド理論的構造解析手法を精密化し,内部自由度を有するシステムの設計変数選択の下での組合せ論的正準形(CGF)分解の共通細分がある種の劣モジュラ関数の基本構造によって特徴づけられることが明らかになった.この結果を,より一般的な立場から考察し,その応用範囲を拡げていくことが望まれる.
分散システムの耐故障性に関連して,二面体群によって記述される対称性を有するシステムの自律可制御性を解析する手法を開発した.
多項式・有理式行列の小行列式の最大次数を組合せ最適化算法を利用して,高速かつ正確に求める方法を開発した.この問題は,制御理論における外乱の除去や,代数微分方程式系の初期値設定など,応用範囲が広い.新しい方法を計算機プログラムとして実現し,ある程度大規模な問題に対しても実際に効率的であることを確認した.
日本学術振興会, 一般研究(C), 京都大学, 06650077
