SEARCH
Search DetailsIwata Satoru
| Institute for Integrated Innovations Institute for Chemical Reaction Design and Discovery | Specially Appointed Professor |
Researcher basic information
■ Degree■ URL
researchmap URLホームページURL■ Various IDs
Researcher number
- 00263161
Career
■ CareerCareer
- Nov. 2020 - Present
Hokkaido University, Institute for Chemical Reaction Design and Discovery, 特任教授, Japan - Feb. 2013 - Present
The University of Tokyo, The Graduate School of Information Science and Technology, 教授, Japan - Apr. 2008 - Jan. 2013
Kyoto University, Research Institute for Mathematical Sciences, 教授, Japan - Apr. 2006 - Mar. 2008
Kyoto University, Research Institute for Mathematical Sciences, 助教授・准教授, Japan - Apr. 2001 - Mar. 2007
The University of Tokyo, The Graduate School of Information Science and Technology, 助教授, Japan - Apr. 2000 - Mar. 2001
The University of Tokyo, The Graduate School of Engineering, 助教授, Japan - Apr. 1997 - Mar. 2000
Osaka University, Graduate School of Engineering Science, 講師・助教授 - Apr. 1994 - Mar. 1997
Kyoto University, Research Institute for Mathematical Sciences, 助手, Japan
Research activity information
■ Awards- Mar. 2026, 日本OR学会, 業績賞
- Jun. 2017, ACM SIGACT, Best Paper Award, STOC 2017
- Apr. 2007, 文部科学大臣表彰 若手科学者賞
- Aug. 2003, MPS & AMS, Fulkerson Prize
- Nov. 2002, 日本IBM科学賞
- Apr. 2001, 日本OR学会, 文献賞
- Jul. 1999, 計測自動制御学会, 論文賞
- Sep. 1997, 情報処理学会, 山下記念研究賞
- Biobjective optimization with M-convex functions
Ellen H. Fukuda; Satoru Iwata; Itsuki Nakagawa
Mathematical Programming, 12 Aug. 2026
Scientific journal - Index Analysis of Differential-Algebraic Equation Models for Electric Circuits with Gyrators
Satoru Iwata; Mizuyo Takamatsu
International Journal of Circuit Theory and Applications, Wiley, 04 Apr. 2026, [Peer-reviewed]
English, Scientific journal, 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, 28 Feb. 2026, [Peer-reviewed]
English, Scientific journal, 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, Feb. 2026, [Peer-reviewed]
English, Scientific journal, 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, 12 Jan. 2026
In book, 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), 13 Jun. 2025, [Peer-reviewed]
English, Scientific journal, 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), 21 Oct. 2024, [Peer-reviewed]
English, Scientific journal, 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, 11 Apr. 2024, [Peer-reviewed], [International Magazine]
English, Scientific journal, 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, 28 Mar. 2024, [Peer-reviewed]
English, Scientific journal - 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), 17 Oct. 2023, [Peer-reviewed]
Scientific journal - 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), Dec. 2022, [Peer-reviewed]
International conference proceedings - 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, Jan. 2022, [Peer-reviewed]
Scientific journal, 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, [Peer-reviewed], [Invited]
Scientific journal - A Pfaffian formula for matching polynomials of outerplanar graphs
Satoru Iwata
Optimization Methods and Software, 36, 2-3, 332, 336, Informa UK Limited, May 2021, [Peer-reviewed], [Invited]
Scientific journal - 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, Feb. 2021, [Peer-reviewed], [Internationally co-authored]
Scientific journal - Finding a Stable Allocation in Polymatroid Intersection
Satoru Iwata; Yu Yokoi
Mathematics of Operations Research, 45, 1, 63, 85, Feb. 2020, [Peer-reviewed]
English, Scientific journal - 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, Jan. 2020, [Peer-reviewed]
English, International conference proceedings - Index Reduction for Differential-Algebraic Equations with Mixed Matrices
Satoru Iwata; Taihei Oki; Mizuyo Takamatsu
Journal of the ACM, 66, 5, 1, 34, Sep. 2019, [Peer-reviewed]
English, Scientific journal - 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, 15 Jan. 2019
English, Scientific journal - List Supermodular Coloring
Satoru Iwata; Yu Yokoi
Combinatorica, 38, 6, 1437, 1456, Dec. 2018, [Peer-reviewed]
English, Scientific journal - Counting Minimum Weight Arborescences
Koyo Hayashi; Satoru Iwata
Algorithmica, 80, 12, 3908, 3919, Dec. 2018, [Peer-reviewed]
English, Scientific journal - Index Reduction via Unimodular Transformations
Satoru Iwata; Mizuyo Takamatsu
SIAM Journal on Matrix Analysis and Applications, 39, 3, 1135, 1151, Jul. 2018, [Peer-reviewed]
English, Scientific journal - 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, Jun. 2018, [Peer-reviewed]
International conference proceedings - Making Bipartite Graphs DM-Irreducible
Kristof Berczi; Satoru Iwata; Jun Kato; Yutaro Yamaguchi
SIAM Journal on Discrete Mathematics, 32, 1, 560, 590, Feb. 2018, [Peer-reviewed], [Internationally co-authored]
English, Scientific journal - 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, [Peer-reviewed]
English, International conference proceedings - 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, [Peer-reviewed]
English, International conference proceedings - 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, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed] - 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, [Peer-reviewed]
International conference proceedings - 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, [Peer-reviewed]
International conference proceedings - 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, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed]
Scientific journal - "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, Sep. 2015, [Peer-reviewed]
English - 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, Sep. 2015, [Peer-reviewed]
English, Scientific journal - Computing the Signed Distance between Overlapping Ellipsoids
Satoru Iwata; Yuji Nakatsukasa; Akiko Takeda
SIAM Journal on Optimization, 25, 4, 2359, 2384, 2015, [Peer-reviewed]
English, Scientific journal - Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity
Satoru Iwata; Tibor Jordan
Discrete Optimization, 12, 121, 128, May 2014, [Peer-reviewed]
English, Scientific journal - 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
English, International conference proceedings - Graph-TSP from Steiner Cycles
Satoru Iwata; Alantha Newman; R. Ravi
WG, 312, 323, 2014, [Peer-reviewed] - 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, [Peer-reviewed] - Global Optimization Methods for Extended Fisher Discriminant Analysis
Satoru Iwata; Yuji Nakatsukasa; Akiko Takeda
Artificial Intelligence and Statistics, 33, 411, 419, 2014, [Peer-reviewed]
English, International conference proceedings - 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, [Peer-reviewed]
English, International conference proceedings - 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, [Peer-reviewed]
English, International conference proceedings - Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
Satoru Iwata; Mizuyo Takamatsu
Algorithmica, 66, 2, 346, 368, Jun. 2013, [Peer-reviewed]
English, Scientific journal - Approximating Max-Min Weighted T-joins
Satoru Iwata; Ramamoorthi Ravi
Operations Research Letters, 41, 4, 321, 324, 2013, [Peer-reviewed] - 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, [Peer-reviewed]
English, Scientific journal - Tractability Index of Hybrid Equations for Circuit Simulation
Satoru Iwata; Mizuyo Takamatsu; Caren Tischendorf
Mathematics of Computation, 81, 278, 923, 939, Apr. 2012, [Peer-reviewed]
English, Scientific journal - Learning Valuation Functions
Maria Florina Balcan; Florin Constantin; Satoru Iwata; Lei Wang
The Twenty-Fifth Conference on Learning Theory (COLT'12), 1, 24, 2012, [Peer-reviewed] - 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, [Peer-reviewed] - A Flow Model Based on Polylinking Systems
Michel X. Goemans; Satoru Iwata; Rico Zenklusen
Mathematical Programming, 135, 1, 23, 2012, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed]
English, International conference proceedings - 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, May 2010, [Peer-reviewed]
English, Scientific journal - An Algorithm for Minimum Cost Arc-Connectivity Orientations
Satoru Iwata; Yusuke Kobayashi
Algorithmica, 56, 4, 437, 447, Apr. 2010, [Peer-reviewed]
English, Scientific journal - Minimum Average Cost Clustering
Kiyohito Nagano; Satoru Iwata; Yoshinobu Kawahara
Twenty-fourth Conference on Neural Information Processing Systems (NIPS'10), 1759, 1767, 2010, [Peer-reviewed] - Index Minimization of Differential-Algebraic Equations in Hybrid Analysis for Circuit Simulation
Satoru Iwata; Mizuyo Takamatsu
Mathematical Programming, 121, 1, 105, 121, Jan. 2010, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed]
English, International conference proceedings - 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, [Peer-reviewed] - 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, [Peer-reviewed] - Computing the Degrees of All Cofactors in Mixed Polynomial Matrices
Satoru Iwata; Mizuyo Takamatsu
SIAM Journal on Discrete Mathematics, 23, 2, 647, 660, 2009, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed]
English, International conference proceedings - Recent Results on Well-Balanced Orientations
Attila Bernath; Satoru Iwata; Tamas Kiraly; Zoltan Kiraly; Zoltan Szigeti
Discrete Optimization, 5, 4, 663, 676, Nov. 2008, [Peer-reviewed]
English, Scientific journal - Index Reduction for Differential-Algebraic Equations by Substitution Method
Mizuyo Takamatsu; Satoru Iwata
Linear Algebra and Its Applications, 429, 8-9, 2268, 2277, Oct. 2008, [Peer-reviewed]
English, Scientific journal - Solving Linear Programs from Sign Patterns
Satoru Iwata; Naonori Kakimura
Mathematical Programming, 114, 2, 393, 418, Aug. 2008, [Peer-reviewed]
English, Scientific journal - Finding Coherent Cyclic Orders in Strong Digraphs
Satoru Iwata; Takuro Matsuda
Combinatorica, 28, 83, 88, 2008, [Peer-reviewed] - Submodular Function Minimization
Satoru Iwata
Mathematical Programming, 112, 45, 64, 2008, [Peer-reviewed] - The Independent Even Factor Problem
Satoru Iwata; Kenjiro Takazawa
SIAM Journal on Discrete Mathematics, 22, 4, 1411, 1427, 2008, [Peer-reviewed]
English, Scientific journal - Computing the Inertia From Sign Patterns
Naonori Kakimura; Satoru Iwata
Mathematical Programming, 110, 1, 229, 244, Jun. 2007, [Peer-reviewed]
English, Scientific journal - 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, [Peer-reviewed] - 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, [Peer-reviewed] - Combinatorial Analysis of Singular Matrix Pencils
Satoru Iwata, Ryo Shimizu
SIAM Journal on Matrix Analysis and Applications, 29, 245, 259, 2007, [Peer-reviewed] - Linking Systems and Matroid Pencils
Satoru Iwata
Journal of the Operations Research Society of Japan, 50, 315, 324, 2007, [Peer-reviewed] - 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, [Peer-reviewed]
English, International conference proceedings - Bisubmodular Function Minimization
Satoru Fujishige; Satoru Iwata
SIAM Journal on Discrete Mathematics, 19, 1065, 1073, 2006, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - Matroid Matching via Mixed Skew-Symmetric Matrices
James Geelen; Satoru Iwata
Combinatorica, 25, 187, 215, 2005, [Peer-reviewed] - 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, [Peer-reviewed] - A Capacity Scaling Algorithm for M-Convex Submodular Flow
Satoru Iwata; Satoko Moriguchi; Kazuo Murota
Mathematical Programming, 103, 181, 202, 2005, [Peer-reviewed] - 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, [Peer-reviewed] - A Network Flow Approach to Cost Allocation for Rooted Trees
Satoru Iwata; Nozomu Zuiki
Networks, 44, 297, 301, 2004, [Peer-reviewed] - A Constrained Independent Set Problem for Matroids
Tamás Fleiner; Andras Frank; Satoru Iwata
Operations Research Letters, 32, 23, 26, 2004, [Peer-reviewed] - Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
Satoru Iwata
Algorithmica, 36, 331, 341, 2003, [Peer-reviewed] - The Linear Delta-Matroid Parity Problem
James F. Geelen; Satoru Iwata; Kazuo Murota
Journal of Combinatorial Theory, Series B, 88, 377, 398, 2003, [Peer-reviewed] - Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
Combinatorica, 23, 503, 525, 2003, [Peer-reviewed] - 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, [Peer-reviewed] - A Faster Scaling Algorithm for Minimizing Submodular Functions
Satoru Iwata
SIAM Journal on Computing, 32, 4, 833, 840, 2003, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - On Matroid Intersection Adjacency
Satoru Iwata
Discrete Mathematics, 242, 277, 281, 2002, [Peer-reviewed] - Locating Sources to Meet Flow Demands in Undirected Networks
Kouji Arata; Satoru Iwata; Kazuhisa Makino; Satoru Fujishige
Journal of Algorithms, 42, 54, 68, 2002, [Peer-reviewed] - A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow
Lisa Fleischer; Satoru Iwata; S. Thomas McCormick
Mathematical Programming, 92, 119, 139, 2002, [Peer-reviewed] - Conjugate Scaling Algorithm for Fenchel-type Duality in Discrete Convex Optimization
Satoru Iwata; Maiko Shigeno
SIAM Journal on Optimization, 13, 204, 211, 2002, [Peer-reviewed] - A Fully Combinatorial Algorithm for Submodular Function Minimization
Satoru Iwata
Journal of Combinatorial Theory, Series B, 84, 2, 203, 212, 2002, [Peer-reviewed] - A Descent Method for Submodular Function Minimization
Satoru Fujishige; Satoru Iwata
Mathematical Programming, 92, 387, 390, 2002, [Peer-reviewed] - Bisubmodular Function Minimization
Satoru Fujishige; Satoru Iwata
Proceedings of the Eighth International Conference on Integer Programming and Combinatorial Optimization, 160, 169, 2001, [Peer-reviewed] - Combinatorial Relaxation Algorithm for Mixed Polynomial Matrices
Satoru Iwata; Kazuo Murota
Mathematical Programming, 90, 353, 371, 2001, [Peer-reviewed] - A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions
Satoru Iwata; Lisa Fleischer; Satoru Fujishige
Journal of the ACM, 48, 4, 761, 777, 2001, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - Algorithms for Submodular Flows
Satoru Fujishige; Satoru Iwata
IEICE Transactions on Information and Systems, E83-D, 322, 329, 2000, [Peer-reviewed] - 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, [Peer-reviewed] - A Fast Cost Scaling Algorithm for Submodular Flow
Satoru Iwata; S. Thomas McCormick; Maiko Shigeno
Information Processing Letters, 74, 123, 128, 2000, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - Minimizing a Submodular Function Arising from a Concave Function
Satoru Fujishige; Satoru Iwata
Discrete Applied Mathematics, 92, 211, 215, 1999, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - Block-Triangularization of Skew-Symmetric Matrices
Satoru Iwata
Linear Algebra and Its Applications, 273, 215, 226, 1998, [Peer-reviewed] - Fast Bipartite Network Flow Algorithms for Assembly and Scheduling
Satoru Iwata; Tomomi Matsui; S. Thomas McCormick
Operations Research Letters, 22, 137, 143, 1998, [Peer-reviewed] - 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, [Peer-reviewed] - A Cost-Scaling Algorithm for 0-1 Submodular Flows
Maiko Shigeno; Satoru Iwata
Discrete Applied Mathematics, 73, 261, 273, 1997, [Peer-reviewed] - A Capacity Scaling Algorithm for Convex Cost Submodular Flows
Satoru Iwata
Mathematical Programming, 76, 299, 308, 1997, [Peer-reviewed] - A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
Satoru Iwata; Kazuo Murota; Maiko Shigeno
Mathematics of Operations Research, 22, 803, 813, 1997, [Peer-reviewed] - 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
In book - 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, [Peer-reviewed] - 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, [Peer-reviewed] - 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, [Peer-reviewed] - A Theorem on the Principal Structure for Independent Matchings
Satoru Iwata; Kazuo Murota
Discrete Applied Mathematics, 61, 229, 244, 1995, [Peer-reviewed] - Principal Structure of Submodular Systems and Hitchcock-type Independent Flows,
Satoru Iwata
Combinatorica, 15, 515, 532, 1995, [Peer-reviewed] - 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, [Peer-reviewed] - A Dual Approximation Approach to Weighted Matroid Intersection
Maiko Shigeno; Satoru Iwata
Operations Research Letters, 18, 153, 156, 1995, [Peer-reviewed] - 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, [Peer-reviewed] - H-infinity Optimal Control for Symmetric Linear Systems
Satoru Iwata
Japan Journal of Industrial and Applied Mathematics, 10, 97, 107, 1993, [Peer-reviewed]
- 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, Nov. 2020, [Peer-reviewed]
English, Others - 2本の2次制約付き非凸2次計画問題に対する多項式時間アルゴリズム
坂上 晋作; 中務 佑治; 武田 朗子; 岩田 覚, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015, 166, 167, 26 Mar. 2015
公益社団法人日本オペレーションズ・リサーチ学会, Japanese - Exact SVM Training by Wolfe's Minimum Norm Point Algorithm
KITAMURA Masashi; TAKEDA Akiko; IWATA Satoru, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 114, 306, 65, 71, 17 Nov. 2014
本論文では,凸多面体上のノルム最小点を有限回の反復で厳密に計算するWolfeのアルゴリズムを,ヒンジロス付きSVMの学習に適用する.提案手法が,LIBSVM等の既存手法よりも速く動作することを数値実験によって示す.また,元の問題の変種問題を解くことで高速化を図ったLIBLINEARと比較しても,サンプル数が特徴数より十分多い時には,提案手法の方が高精度の判別器を高速に構成することを数値実験で確認する., The Institute of Electronics, Information and Communication Engineers, Japanese - 2-A-5 Wolfeの最小ノルム点アルゴリズムによるSVM学習
北村 昌士; 武田 朗子; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2014, 170, 171, 28 Aug. 2014
公益社団法人日本オペレーションズ・リサーチ学会, Japanese - 電力網のサイバー攻撃に対する安全性評価 : ハイパーグラフ最小カット問題の応用
山口 勇太郎; 小川 安奈; 武田 朗子; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2014, 206, 207, 28 Aug. 2014
公益社団法人日本オペレーションズ・リサーチ学会, Japanese - Releasing Discrete Convex Optimization Solvers and Demonstration Softwares
土村 展之; 森口 聡子; 垣村 尚徳; 岩田 覚; 室田 一雄, 研究報告アルゴリズム(AL), 2011, 4, 1, 6, 05 Jan. 2011
マトロイド・劣モジュラ関数の研究の流れを汲んだ離散凸解析による統一的枠組みの中で,離散最適化問題を効率的に解く各種アルゴリズムが提案されてきた.離散凸解析理論の普及を目的として,これらの成果を応用分野の研究者・実務家が享受できるように,関連するアルゴリズムを紹介するデモンストレーションソフトウェアと,アプリケーションソフトウェアを開発した.ソルバ及びデモンストレーションソフトウェアの 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., 情報処理学会, Japanese - 1-B-6 線形計画問題の符号可解性
垣村 尚徳; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2005, 38, 39, 14 Sep. 2005
公益社団法人日本オペレーションズ・リサーチ学会, Japanese - 符号対称行列のSylvester指数
垣村 尚徳; 岩田 覚, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2004, 228, 229, 08 Sep. 2004
公益社団法人日本オペレーションズ・リサーチ学会, Japanese - 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
English, Book review
- Matroid Parity
Satoru Iwata
The Twelfth Annual Meeting of the Asian Association for Algorithms and Computation (AAAC), 2019
[Invited] - Weighted Linear Matroid Parity
Satoru Iwata
The Twenty-Eighth International Symposium on Algorithms and Computation (ISAAC), 2017
[Invited] - Submodular Functions: Optimization and Approximation
Satoru Iwata
International Congress of Mathematicians (ICM), 2010
[Invited] - Submodular Function Minimization under Covering Constraints
Satoru Iwata; Kiyohito Nagano
The Sixth Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2009
[Invited] - Approximating Submodular Functions
Satoru Iwata
Lunteren Conference on Mathematics of Operations Research, Jan. 2009
[Invited] - Minimizing Submodular Functions
Satoru Iwata
Lunteren Conference on Mathematics of Operations Research, Jan. 2009
[Invited] - Submodular Functions
Satoru Iwata
ADONET-CIRM School on Graphs and Algorithms, Oct. 2007
[Invited] - 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, Apr. 2007
[Invited] - Submodular Function Minimization
Satoru Iwata
The Nineteenth International Symposium on Mathematical Programming, Aug. 2006
[Invited] - Submodular Function Minimization
Satoru Iwata
International Conference on High Performance Scientific Computing, Mar. 2006
[Invited] - Combinatorial Approaches to Matrix Pencils
Satoru Iwata
The Third Sino-Japanese Optimization Meeting, Nov. 2005
[Invited] - Linking Systems and Matroid Pencils
Satoru Iwata
The Fourth Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Jun. 2005
[Invited]
- Developing Optimization Methods for Chemical Reaction Prediction, Design and Control
Strategic Basic Research Programs
Oct. 2024 - Mar. 2030
Satoru Iwata; Wataru Matsuoka; Taihei Oki
本研究課題は、量子化学計算と数理最適化を融合して、触媒や反応条件の最適設計を行う方法論の構築を目的としています。そのために、分子の電子効果・立体効果を近似するバーチャル分子モデルを導入します。さらに、触媒や反応条件の各パラメータ値が収率や選択性に及ぼす影響の偏導関数値を用いて最適パラメータ値を算出し、これを近似的に実現する分子や条件を選択することにより化学反応を最適化する方法論を確立します。
Japan Science and Technology Agency, CREST, The University of Tokyo, JPMJCR24Q2 - Development and Applications of Methods for Determination of Three-Dimensional Molecular Structures
Grants-in-Aid for Scientific Research
01 Apr. 2021 - 31 Mar. 2026
佐藤 寛子; 岩田 覚
分子の立体的な構造は活性や物性を決める重要な要素の1つであり,近年のコンピュータ性能の向上によって高精度かつ大規模な3次元(3D)分子構造データの獲得と蓄積が可能となってきた。本研究では,データサイエンスの活発化と相まって今後さらに活発化すると期待される3D分子データ活用のための新技術の確立と実証を目指し,データ化学と離散情報学を融合させた効率的アルゴリズムを開発し,分子の3D幾何構造に関する応用研究を実施する。具体的には,我々が最近開発した汎用的3D分子類似度判定法G-RMSDを中心に新規アルゴリズムを開発し,分子設計や化学反応予測等における従来法では困難な問題の解決に挑戦する。
令和3年度は以下の3点について重点的に研究を実施した。
まず,G-RMSDを中心とした新規アルゴリズムの1つとして,分子間のRMSD最小値の最適解を保証する厳密解法を開発,実装した。2点目として,商用ソフトウェアMATLABで動くG-RMSDプログラムコードをフリーオープンソースコードOctaveに移植し,汎用性を向上させた。3点目として,分子動力学シミュレーションによる化学反応過程に存在する点としてサンプリングされる分子構造群を最もエネルギーの低い経路を辿る線で繋ぐ最安定経路を同定する新手法開発の基礎データとなる分子動力学シミュレーションを実施した。
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), 大学共同利用機関法人情報・システム研究機構(機構本部施設等), 21K11776 - New computational models for algorithms and discrete optimization
Grants-in-Aid for Scientific Research
19 Nov. 2020 - 31 Mar. 2025
河原林 健一; 岩田 覚; 吉田 悠一; 福永 拓郎; 平原 秀一; Avis David
現在の情報検索技術(GoogleのPageRank)、セキュリティ技術(Appleの(Local) Differential Privacy)などのアルゴリズム革新は国家規模のビジネス創成につながり、現在のGAFAを作り上げた。ここで重要なのは、PageRankもDifferential Privacyもアルゴリズムおよび理論計算機科学、離散数学の基礎・理論研究であり、最初から応用を志向した仕事ではない点である。このような事実をMicrosoft、IBM、Google、Yahoo、Facebook、Amazonなどの巨大 IT企業は創業当初から認識しており、現在でもアルゴリズム、離散数学に手厚いサポートをしている。
本研究では、このような背景を踏まえ、理論分野のさらなる強化、特にグラフアルゴリズム、計算量理論、組合せ最適化のそれぞれの分野での世界的な研究成果発信と学術変革を目指す。またこれらを通して研究領域内での「人材育成」および、コロナ期における世界的なアルゴリズム国際共同研究拠点構築を目指す。
Japan Society for the Promotion of Science, Grant-in-Aid for Transformative Research Areas (A), National Institute of Informatics, 20H05965 - 前田化学反応創成知能プロジェクト
戦略的な研究開発の推進 戦略的創造研究推進事業 ERATO
2019 - 2024
前田 理; 岩田 覚
本プロジェクトでは、世界に先駆けて開発した反応経路自動探索技術(AFIR法)と、組合せ最適化技術を基盤とし、量子化学計算、情報科学、さらにはマテリアルズ・インフォマティクスの技術を統合することで、化学反応における「原子の動きの全貌」を予測し、有用な未知の化学反応を次々に提案する「化学反応創成知能」を創出します。 具体的には、AFIR法を用い、さまざまな反応物や触媒の組み合わせに対して「反応経路ネットワーク」を計算し、得られる反応経路データベースから目的物合成に適した化学反応を迅速に設計・提案するシステムを構築します。このとき、目的生成物の収率が最大となる反応物の組み合わせを導くために、組合せ最適化技術を活用します。また、反応経路ネットワークから反応性を支配する因子を抽出し、分子構造との相関を学習させることで、反応性を言い当てられる機械を創出します。 また、「化学反応創成知能」は実験的には検出できない超微量な副生物の存在まで明らかにできるため、そこから未知の化学反応が発見される期待もあります。さらに、合成ロボットへの「化学反応創成知能」の実装を試み、目的とする物質を生成するのに最適な化学反応を発見するスピードを大幅に加速することを目指します。
科学技術振興機構, 北海道大学 - Development of Global Optimization Methods by Generalized Eigenvalue Computation
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
01 Apr. 2017 - 31 Mar. 2022
Iwata Satoru
While non-convex optimization problems are hard to solve in general, this research has focused on those problems that have geometrical backgrounds and investigated a methodology to design efficient algorithms for obtaining globally optimal solutions. In particular, we have developed an efficient algorithm for non-convex quadratic constraint quadratic programming (QCQP) with one constraint. In addition, we exploit this algorithm to obtain relaxation solutions for general non-convex QCQP with the aid of the Lagrange multipliers.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), The University of Tokyo, 17H01699 - Global Optimization Methods by Generalized Eigenvalue Computation
Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Exploratory Research
01 Apr. 2014 - 31 Mar. 2017
Iwata Satoru
Nonconvex optimization is believed to refuse any efficient algorithms in general. This project has aimed at developing a method to design efficient algorithms for nonconvex optimization problems that arises with a geometric background, exploiting their structures. In particular, we have designed an algorithm for computing the signed distance between overlapping ellipsoids. The running time is O(n^6), where n is the dimension of the space. We have extended this approach to solve the generalized CDT problem in the same running time. We have also reduced the trust-region subproblem, which is repeatedly solved in the trust-region method, to a generalized eigenvalue problem, and shown that this reduction leads to an efficient and accurate solution method with the aid of today's highly developed solvers for the generalized eigenvalue problem.
Japan Society for the Promotion of Science, Grant-in-Aid for Challenging Exploratory Research, The University of Tokyo, 26540007 - Deepening analysis methods for limits of computation through integration with optimization techniques
Grants-in-Aid for Scientific Research
28 Jun. 2012 - 31 Mar. 2017
Katoh Naoki
In this project, we obtained the following results.
1. On extended formulations that have been extensively studied recently, a compact representation is provided for sparsity matroids that play important roles both in theory and in practice. 2. The first polynomial-time algorithm is developed for the weighted linear matroid parity problem. 3. A novel reduction method (a hardness proof method) is developed among problems for which brute-force searches cannot be essentially surpassed, resulting in a new standard for the field of exponential-time computation. 4. A polynomial time deterministic approximation algorithm is presented to compute the volume of a 0-1 knapsack polytope which is known to be #P-hard.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), 24106005 - Approximation Algorithms for Submodular Optimization
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
01 Apr. 2011 - 31 Mar. 2016
Iwata Satoru; TAKAZAWA Kenjiro; TANIGAWA Shin-ichi
Submodularity is known to be a common structure among various efficiently solvable discrete optimization problems. On the other hand, most discrete optimization problems that arise in practice are NP-hard, and researchers have designed efficient algorithms for finding approximately optimal solutions. Combining these two streams of research in discrete optimization, we have tried to develop a systematic approach to design approximation algorithms for a generic framework of submodular optimization. In particular, we have provided a 1/2-approximation algorithm for maximizing k-submodular functions. We have also designed an approximation algorithm for maximizing monotone k-submodular functions within the ratio of k/2(k-1).
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), 23300002 - Unified Optimization Theory by Discrete Convex Paradigm
Grants-in-Aid for Scientific Research
01 Apr. 2009 - 31 Mar. 2015
MUROTA Kazuo; TAMURA Akihisa; IWATA Satoru; SHIOURA Akiyoshi; MORIGUCHI Satoko; KAKIMURA Naonori; KOBAYASHI Yusuke; TSUCHIMURA Nobuyuki
This research integrated the theory and application of optimization in various fields of engineering and social sciences by Discrete Convex Paradigm. We analyzed the theory and applications of discrete convex analysis, to clarify the mutual relationship of the individual mathematical techniques and problems in applications, from three aspects of the continuous-discrete axis, the convex-nonconvex axis, and the fields-transversal axis. Also we conducted research from three aspects of mathematical deepening, applications development, and software development, and achieved the new developments in Discrete Convex Paradigm. In particular, mathematical deepening includes the results of detailed analysis in L-convex function minimization algorithm and presentation of a framework of discrete DC programming.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), The University of Tokyo, 21360045 - Algorithm developments for network structure analysis and comprehensive expansions of network algorithms
Grants-in-Aid for Scientific Research
2010 - 2012
SHIGENO Maiko; YAMAMOTO Yoshitsugu; YOSHISE Akiko; HACHIMORI Masahiro; IWATA Satoru
This research analyzed network structures in social system based on basic theory for network optimization, together with game theory and graph theory.Especially, the following topics were focused: algorithms for community extraction and its evaluation, characteristics for information diffusion network, and analysis of saturated graphs. In addition, we showed the possibility of approach using network theory for vertical machine location, auction, staff scheduling, and taxi allocation.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), University of Tsukuba, 22510135 - Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
Grants-in-Aid for Scientific Research
2008 - 2012
FUJISHIGE Satoru; IWATA Satoru; MAKINO Kazuhisa; KIJIMA Shuji; HIRAI Hiroshi
We have investigated large-scale discrete optimization problems by paying special attention to submodular structures which are effective to devise efficient algorithms. Specifically we have examined discrete optimization problems related to network flows, matchings, multiflows, facility location, resource allocation,graph connectivity, communication network design, and queueing networks, discrete structures arisen in dual greedy algorithms such as dual greedy polyhedra and zonotopes,discrete structures for Horn functions and stable matching problems, and so on to establish the fundamental theory and fast algorithms by integrating the knowledge and insights gained on the individual discrete structures.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 20310088 - Index Reduction Methods for Differential-Algebraic Equation Models by Discrete Optimization Techniques
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
2008 - 2010
IWATA Satoru; TAKAMATSU Mizuyo; TISCHENDORF Caren
Large-scale dynamical systems, such as integrated circuits and chemical plants, are naturally described by differential-algebraic equations (DAEs). However, numerical solution of DAEs is often much more difficult than that of ODEs. This research focuses on DAEs arising in circuit simulation and establishes an efficient method to obtain a differential-algebraic equation model that is the easiest to solve numerically.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), Kyoto University, 20560057 - Development of theoretical foundation and extension on networks
Grants-in-Aid for Scientific Research
2007 - 2009
SHIGENO Maiko; YAMAMOTO Yoshitsugu; YOSHISE Akiko; HACHIMORI Masahiro; IWATA Satoru
On network theory, this research established fundamental theory to advance growth of field, and expanded models to enlarge its domain to real-world problems more. For both of basic and ecpanded network problems, efficient algorithms were developed. Especially, the following topics were focused : an efficient algorithm for location problem on a network with adjustability, new parameters for fault tolerance communication networks, community extraction approach on hypergraps, and graph orientation.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), University of Tsukuba, 19510137 - Deepening and Expansion of Discrete Convexity Paradigm
Grants-in-Aid for Scientific Research
2006 - 2008
MUROTA Kazuo; TAMURA Akihisa; IWATA Satoru; TSUCHIMURA Nobuyuki; MORIGUCHI Satoko; SHIOURA Akiyoshi
経済学,システム工学,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立し,それを広範囲の応用分野に浸透させる研究を行った.「離散凸パラダイム」の横糸を成す,構造定理やアルゴリズムを代表とする離散関数に関する数理の研究と,縦糸を成す,諸応用分野における具体的な諸問題に対する研究を行った.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), The University of Tokyo, 18360048 - 離散最適化技法による行列束のロバスト数値計算とシステム解析への応用
科学研究費助成事業 若手研究(B)
2005 - 2007
岩田 覚
行列束のKronecker標準形は,微分代数方程式で記述される動的システムの解析において本質的な役割を果たしている.しかし,標準形の摂動に対する感度が非常に高く,計算誤差の発生しうる数値計算によって正確な標準形を得ることには困難を伴う.
本研究課題では,計算誤差が発生し得ない組合せ的計算を利用することによって数値計算の負担を減らして,できるだけ正確な標準形を安定に計算する手法を確立することを目的としている.従来の研究の結果,Kronecker標準形の構造指数のうち,冪零指数に関して,2部グラフ上の最大重みマッチングを利用した組合せ緩和法が確立されている.本研究課題は,組合せ緩和法に基づいて行指数・列指数を計算するアルゴリズムの設計と計算機上での実現を目的としている.
昨年度までの研究成果より,周期的な構造を有する2部グラフ上の最大マッチングを計算することによって,行指数・列指数の推定値が得られることが明らかとなった.
本年度は,引き続き,組合せ緩和法の設計に取り組み,世界標準的なソフトであるGUPTRIで採用されているアルゴリズムよりも効率的な新たなアルゴリズムを得た.しかし,計算精度に関しては,GUPTRIの方が優れているため,現時点では,組合せ的な推定値とGUPTRIとを併用するのが,最も適切な計算法であるとの結論に達した.
また,微分代数方程式の指数減少法への応用研究を行い,電気回路の数値解析手法として知られる混合解析の枠組みにおいて,最小指数を達成する微分代数方程式を導出する効率的なアルゴリズムを開発した.
日本学術振興会, 若手研究(B), 17760065 - 連続と離散の融合によるロバストアルゴリズム構築
科学研究費助成事業
2004 - 2007
杉原 厚吉; 室田 一雄; 今井 浩; 松井 知己; 岩田 覚; 大石 泰章
従来は連続計算の分野と離散計算の分野に分かれてそれぞれ独立になされてきたアルゴリズム研究の知見を融合し,両者の手法の長所を補完し合うことによって,諸計算のロバスト性を確保するための計算原理を開拓することが本研究の目的であった.本年度もこの目的に沿って研究を行い,次のような成果を得た.幾何計算の分野では,2次元および3次元の球ボロノイ図のロバストな計算法を開発した.これは,位相構造をいつも正しく判定できる高精度計算を用いるもので,必要な精度をもとの入力データの2d+4倍に置き換えることに成功した.また,流れの中でのボートの最短経路を求めるロバスト解法を高次元と曲面上とへ拡張した.さらに長方形詰込み問題の実用的解法を構成するとともに,一般の形の図形詰込み結果に基づいてハードメタルを切り取るためのカッターパス生成法を構成した.離散凸解析の分野では,定パリティジャンプシステム上のM凸関数が,合成積やグラフによる変換によってM凸性を保存することを示した.量子計算の分野では,カット凸多面体とベル不等式の関係を明らかにし,量子状態を記述するより強力な不等式を得た.サンプリングの分野では,マルコフ連鎖を用いたモンテカルロ法のためのパーフェクトサンプリング方法を開発した.組合せ最適化の分野では,数理計画問題の符号情報のみから最適解の性質を調べる方法を開発した.制御計算の分野では,制御対象パラメータのとり得る区間の中で常に安定性が保証されるロバスト制御法を,ロバスト線形不等式を条件とする半正定値問題に帰着させて解く方法を与えた.構造設計の分野では,不確定な外力に対する構造物の解析法を開発した.これらの諸成果を通じて,「連続計算における知見と離散計算における知見の交流によって,計算の安定化をはかることができる」というロバストな計算を確保するための一つの原理の有効性を確認することができた.
日本学術振興会, 特定領域研究, 東京大学, 16092204 - Establishment of Discrete Convexity Paradigm
Grants-in-Aid for Scientific Research
2003 - 2005
MUROTA Kazuo; TAMURA Akihisa; IWATA Satoru; TSUCHIMURA Nobuyuki
The main aim of this research project is to establish a novel paradigm of discrete convexity by exploiting applications of the theory of discrete convex analysis to fundamental problems in economics, system engineering, operations research, optimization, algorithm science, and others. In this research project, we obtained a number of results described below. All of the results are presented at refereed international conference or accepted for publications in international scientific journals.
(1)For optimization problems related to discrete convexity (in particular, for the submodular flow problem with M-convex cost function), we developed a number of efficient algorithms using the capacity scaling technique. The obtained algorithm has the best known complexity bound.
(2)We pointed out that the concept of multimodular functions, which had been conceived independently of discrete convex analysis, is essentially equivalent to the concept of L-convex functions. On the basis of this observation we derived some properties including discrete separation.
(3)We revealed a close relationship between M-convex functions and tree metrics. Specifically, we proved that the Hessian matrix of a quadratic M-convex function is essentially the same as the negative of the tree metric matrix.
(4)We established a discrete fixed point theorem for functions defined on integrally convex sets. The theorem finds applications in mathematical economics and game theory.
(5)We provided new characterizations of M-convex functions in terms of gross substitution and single improvement property known in mathematical economics.
(6)As applications of discrete convex analysis to mathematical economics, we developed a theory for economic equilibrium models with indivisible goods. We also developed an algorithm for computing a competitive equilibrium using the framework of M-convex submodular flow problem.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), The University of Tokyo, 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 - Applications of low density party check codes to data compression with distortion
Grants-in-Aid for Scientific Research
2002 - 2003
YAMAMOTO Hirosuke; OGAWA Tomohiro; IWATA Satoru
A LPDC(low density parity check) code is an error correcting code that was first proposed by Gallager in 1962. Recently, BP(belief propagation) or other repeating decoding algorithms become applicable to the LDPC codes by rapid growth of computer power. In this research, we applied the LODC codes to data compression with distortion, and evaluated the performance.
In 2002, we proposed an encoding algorithm to apply the LODC codes to data compression with distortion. Furthermore, we proved that there exits a LODC codes that can attain the theoretical optimal rate, i.e., rate-distortion function. In 2003, we improved the proof and published the results in the IEEE transactions on Information Theory. In the coding theorem, it is shown that if column weight t in the parity check matrix of a LODC codes satisfies t=O(log n) for code length n, the code can attain the rate-distortion function asymptotically. Furthermore, if t=O(n), then it converge to the rate-distortion function exponentially.
We also show by simulation that the BP algorithm of LPDC codes for error correcting cannot attain a good performance in the case of rate-distortion coding.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), Kazunori Hoshino,, 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 - Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
Grants-in-Aid for Scientific Research
1998 - 2000
FUJISHIGE Satoru; SHIGENO Maiko; MAKINO Kazuhisa; IWATA Satoru; TAKABATAKE Takashi
The objective of this research project is to examine the underlying combinatorial structure of optimization problems that can be solved efficiently, and to give a unifying principle for designing efficient algorithms for such a class of combinatorial optimization problems. Our major results of the project are the following.
1. We succeeded in resolving the long-standing open problem of devising a combinatorial (strongly) polynomial algorithm for minimizing submodular functions. This gave great impact on the field of discrete optimization. Following this result, we also developed a fully combinatorial strongly polynomial algorithm for submodular function minimization, and a combinatorial polynomial-time algorithm for bisubmodular function minimization, a generalization of submodular function minimization.
2. The second cluster of results are concerned with network optimization problems. We considered a source location problem with flow requirements in undirected networks and devised a fast algorithm for solving it. Also we developed an efficient algorithm for L_∞-minimax inverse problem of the minimum cut problem by taking a parametric approach, and we obtained a characterization of the so-called polybasic polyhedra that generalize the boundary polyhedra of generalized flows.
3. As the third cluster of results, we developed a polynomial-time algorithm for finding an optimal coterie in distributed systems, and we succeeded in constructing pseudopolynomial-time algorithms for enumerating partial transversals and multiple transversals of hypergraphs arising in the fields of data mining and learning theory.
Besides these results, we revealed the deep underlying relationship between the submodularity and the economic equilibrium analysis by showing the equivalence of the M^?-concavity of the relevant set function and the gross substitutes condition in the matching (or equilibrium) model with indivisible commodities.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Priority Areas (B), Osaka University, 10205217 - Discrete System Theory and Large-Scale Optimization Methods Based on Binary Decision Diagrams and
Grants-in-Aid for Scientific Research
1997 - 2000
IMAI Hiroshi; IWATA Satoru; INABA Mary; ASAI Ken-ichi
In this research, we aimed at proposing a unified approach to discrete system theory based on binary decision diagrams, and developing a prototype system for the unified system. By our results, we can now represent the whole moderate-scale discrete structure in a implicit and compact manner, which could not be done by the existing methods. We applied our approach to network reliability computation and also computing the Jones polynomial of a knot. These computation problems are known to be #P-hard, but, with our methods, moderate-size problems can be solved rigorously in practice. For example, the network reliability function of a grid of 14x14 can be computed. We also explore fundamental theory of binary decision diagrams, by investigating the difference in size when a monotone Boolean function is represented directly and when it is represented by their prime implicants.
New approaches have also been demonstrated, one is based on algebraic approach, and the other is based on quantum approach. Concerning the algebraic approach, Grobner bases are fully investigated for network flow problems. Concerning the quantum approach, we investigate a quantum analog of binary decision diagrams in order to investigate the computational power of quantum computing. These new results will be published soon.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B)., the University of Tokyo, 09480050 - 組合せ最適化技法による代数計算とシステム解析への応用
科学研究費助成事業 奨励研究(A)
1998 - 1999
岩田 覚
動的システムの解析や設計に重要な役割を果たす多項式行列の小行列式の最大次数を求める算法設計の新しい方法論として、代数的手法と組会せ的手法を融合した。『組合せ緩和法』が提唱されている。本研究では、組合せ緩和法の枠組みを尊重しつつ、多項式行列の変形に多くの記憶領域を要するという問題点を克服するために、動的システムの解析や設計に本質的な行列ペンシルに対象を限定した上で、定数行列による行列変換のみを用いた新しい組合せ緩和算法を開発した。この成果を、99年1月にボルチモアで開かれた第10回ACM/SIAM離散アルゴリズム会議で発表した。
行列ペンシルの小行列式の最大次数は、Kronecker標準形の構造指数と密接な関係がある。行列のKronecker標準形を求めるアルゴリズムとしては、従来、反復法を中心とした研究が行われてきたが、本研究を通じて、消去法を基礎とした直接法によって構造指数を求められることが明らかとなった。
組合せ緩和法は、優れて斬新な方法論であるが、未だ実用的なレベルに達してはいない。その原因としては、算法の正当性を理解するために、数値計算の専門家やシステムの解析や設計に携わる技術者に馴染みの薄い、組合せ最適化のかなり高度な議論を必要としていることが挙げられる。この問題点は、使い勝手のよい信頼できるソフトウェアを提供することによって解消されるであろう。
また、行列の組合せ論的な側面を抽象化したマトロイドと不可分の関係にある劣モジュラ関数に関して、多項式時間で最小値を求める組合せ的なアルゴリズムを開発した。
日本学術振興会, 奨励研究(A), 大阪大学, 10750053 - Systems Analysis by Valuated Matroids
Grants-in-Aid for Scientific Research
1997 - 1999
MUROTA Kazuo; SUGIHARA Masaaki; FURIHATA Daisuke; OKAMOTO Hisashi; IWATA Satoru
This project aims at developing algebraic and combinatorial methods for mathematical analysis of engineering systems by means of valuated matroid theory. The following results have been obtained.
(1) Practical improvements are made on the algorithm for constructing the combinatorial canonical form of mixed matrices, so that the mathematical results on mixed matrices can be utilized in systems analysis. The improved algorithm is implemented and made available through internet.
(2) The duality theorem for valuated matroids implies that a mixed polynomial matrix can be brought into a canonical form (a proper rational matrix with additional nice properties) by a suitable change of variables and equations. The algorithm for the valuated matroid duality is tailored to the canonical form of a mixed polynomial matrix.
(3) The relationship between the matroid parity problem and the solvability of RCG (electrical) networks is investigated in detail. The solvability of RCG networks is formulated in terms of mixed skew-symmetric matrices, and the solvability condition is derived with the aid of the duality theorem for a pair of linear delta matroids. This leads to an efficient algorithm for the solvability of RCG networks.
(4) Controllability of distributed control systems with symmetry is discussed under the genericity assumption under symmetry. The problem is formulated using the standard framework of group representation theory and a bound on the number of functioning modules necessary for controllability is derived by means of the Rado-Perfect theorem in matroid theory.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), KYOTO UNIVERSITY, 09450042 - On the research and development of fast solvers arising in scientific computation
Grants-in-Aid for Scientific Research
1997 - 1998
OKAMOTO Hisashi; SASAKI Fumio; TAKANO Shinichiro; SUGIHARA Masaaki; MORI Masatake; MUROTA Kazuo
Progress is made in the study of vortex method, thin layer element method, wavelet, finite difference method. Okamoto published a survey paper on the fundamental solution method. Mr. K.Kobayashi develops, under the guidance of Okamoto, a new algorithm for computing the minimal surfaces. F.Sasaki considers a new application of wavelets to integral equations, in which the conventional wavelets are difficult to be applied because of the nonlocality of the integral equations. K.Murota and S.Iwata develop a unified theory for the mixed matrices. They write a program to compute the combinatorial canonical form of the mixed matrices and made it available through internet. M.Sugihara considers theoretical background of the fundamental solution method. In particular he proposes a new method of locating the singularities in three-dimensional domain. He also applies the double exponential transform to the Sinc method of functional approximation. His results show that the double exponential transform is of the optimal order in the Sinc method. Y.Iso considers a numerical method for inverse scattering problem. He shows that a certain high precision numerical software is very effective. T.Ikeda performs numerical experiments of the parallel computation for the reaction-diffusion equation. He clarifies some of the theoretical background of basic algorithms in the parallel computation, ] which has been only heuristically derived.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 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 - Joint Research on Algorithms in Computational Geometry
Grants-in-Aid for Scientific Research
1994 - 1995
IMAI Hiroshi; ASAI Kenichi; IWATA Satoru; TSUCHIYA Takashi; INAGAKI Hiroshi; IMAI Keiko; ASANO Takao; SUGIHARA Kokichi; EDELSBRUNNER Helbert; RAPPAPORT David; TOUSSAINT Godfried; AVIS David
This Grant-in Aid for Scientific Research in the International Scientific Research Program for Joint Research of the Ministry of Education, Science, Sports and Culture of Japan have been carried out for 1994 and 1995 academic years. This project was applied to the program by bringing making active researchers in computational geometry in Japan, Canada and US together to work out for new topics in the field based on the establishments of each member of this group. In fact, some of the group members had chances to work together in Canada and Japan for a short period, but such joint research was a very small-scale one due to the constraints about the time and the number of members. By this project, all the researchers in our group can gather together to discuss the most active topics nowadays.
By this project, we have developed the theory of geometric enumeration, generation and counting based on the techniques proposed by our members. Specifically, reverse search, binary decision diagrams and polytopal approaches are demonstrated to be powerful tools to solve geometric problems of large size which could not be solved by the existing methods. This was achieved by exchanging ideas in Canada and Japan several times based on this Grant-in-Aid. In fact, the international cooperation between our group has been extended to Asian/Pacific Area by attracting many research in these areas to join us.
Our results have been published as is seen from the list of papers. A notable publication in Japanese is a book by David Avis and Hiroshi Imai on Computational Geometry. About the programming package on triangulations, a technical presentation and a video presentation will be done at the 12th ACM Symposium on Computational Geometry this year, which is one of the biggest event in the field.
Japan Society for the Promotion of Science, Grant-in-Aid for international Scientific Research, University of TOKYO, 06044058 - 組合せ理論と群表現論に基づく大規模システムの構造解析手法の研究
科学研究費助成事業
1994 - 1994
岡本 久; 岩田 覚
1.大規模方程式系に関するマトロイド理論的構造解析手法を精密化し,内部自由度を有するシステムの設計変数選択の下での組合せ論的正準形(CGF)分解の共通細分がある種の劣モジュラ関数の基本構造によって特徴づけられることが明らかになった.この結果を,より一般的な立場から考察し,その応用範囲を拡げていくことが望まれる.
分散システムの耐故障性に関連して,二面体群によって記述される対称性を有するシステムの自律可制御性を解析する手法を開発した.
多項式・有理式行列の小行列式の最大次数を組合せ最適化算法を利用して,高速かつ正確に求める方法を開発した.この問題は,制御理論における外乱の除去や,代数微分方程式系の初期値設定など,応用範囲が広い.新しい方法を計算機プログラムとして実現し,ある程度大規模な問題に対しても実際に効率的であることを確認した.
日本学術振興会, 一般研究(C), 京都大学, 06650077
