Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway lines in Tokyo including Keio Line with six types of trains and succeed in relaxing congestion with a small effect on travel time.

DOI： 10.4230/OASIcs.ATMOS.2017.13

Scopus

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1137/17M111794X

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

Consider a linear time-invariant dynamical system that can be described as Fx(t) = Ax(t) + Bu(t), where A, B, and F are mixed matrices, i.e., matrices having two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The controllable subspace of the system is closely related to the Kronecker canonical form of the mixed matrix pencil (A - sF | B). Under a physically meaningful assumption justi fied by the dimensional analysis, we provide a combinatorial characterization of the sums of the minimal row/column indices of the Kronecker canonical form of mixed matrix pencils. The characterization leads to a matroid-theoretic algorithm for efficiently computing the dimension of the controllable subspace for the system with nonsingular F.

DOI： 10.1137/16M1057516

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS INC ELSEVIER SCIENCE  

In circuit simulation, differential-algebraic equations (DAEs) to be solved numerically are obtained through circuit analysis methods. While the modified nodal analysis (MNA) is the most popular method, the hybrid analysis has been shown to have inherent advantage over MNA in terms of index, which is a measure of the numerical difficulty of DAEs. A recent paper of Iwata, Takamatsu, and Tischendorf (2012) has characterized the network structure that leads to DAEs with tractability index zero and one in the hybrid analysis. As a sequel, this paper gives a necessary condition for the hybrid equations to have tractability index at most two. Moreover, we show that this condition is also sufficient for linear time-invariant circuits if dependent sources satisfy a genericity assumption. Since commonly-used circuits fulfill the condition, it is ensured that the hybrid analysis results in a DAE with tractability index at most two in most cases. By combining our results with the previous one, we obtain criteria for tractability index zero/one/two. (C) 2013 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.jmaa.2013.10.018

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

Given an undirected graph G = (V, E) and a delta-matroid (V, F), the delta-matroid matching problem is to find a maximum cardinality matching M such that the set of the end vertices of M belongs to F. This problem is a natural generalization of the matroid matching problem to delta-matroids, and thus it cannot be solved in polynomial time in general. This paper introduces a class of the delta-matroid matching problem, where the given delta-matroid is a projection of a linear delta-matroid. We first show that it can be solved in polynomial time if the given linear delta-matroid is generic. This result enlarges a polynomially solvable class of matching problems with precedence constraints on vertices such as the 2-master/slave matching. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

DOI： 10.1137/110860070

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

Mixed polynomial matrices are polynomial matrices with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The computation of their maximum degrees of minors is known to be reducible to valuated independent assignment problems, which can be solved by polynomial numbers of additions, subtractions, and multiplications of rational functions. However, these arithmetic operations on rational functions are much more expensive than those on constants.
In this paper, we present a new algorithm of combinatorial relaxation type. The algorithm finds a combinatorial estimate of the maximum degree by solving a weighted bipartite matching problem, and checks if the estimate is equal to the true value by solving independent matching problems. The algorithm mainly relies on fast combinatorial algorithms and performs numerical computation only when necessary. In addition, it requires no arithmetic operations on rational functions. As a byproduct, this method yields a new algorithm for solving a linear valuated independent assignment problem.

DOI： 10.1007/s00453-012-9640-8

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：AMER MATHEMATICAL SOC  

Modern modeling approaches for circuit simulation such as the modified nodal analysis (MNA) lead to differential-algebraic equations (DAEs). The index of a DAE is a measure of the degree of numerical difficulty. In general, the higher the index is, the more difficult it is to solve the DAE.
In this paper, we consider a broader class of analysis methods called the hybrid analysis. For nonlinear time-varying circuits with general dependent sources, we give a structural characterization of the tractability index of DAEs arising from the hybrid analysis. This enables us to determine the tractability index efficiently, which helps to avoid solving higher index DAEs in circuit simulation.

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

The use of network analysis has increased in various fields. In particular, a lot of attention has been paid to centrality metrics using shortest paths, which require a comparatively smaller amount of computation, and the global characteristic features within the network. While theoretical and experimental progress has enabled greater control over networks, large amounts of computation required for dealing with large-scale networks is a major hurdle. This research is on high-performance network analysis considering the memory hierarchy in a computer; it targets extremely important kernel types called shortest paths and centrality. Our implementation, called NETAL (NETwork Analysis Library), can achieve high efficiency in parallel processing using many-core processors such as the AMD Opteron 6174, which has the NUMA architecture. We demonstrated through tests on real-world networks that NETAL is faster than previous implementations. In the all-pairs shortest paths for the weighted graph USA-road-d. NY. gr (n. -264K, m -734K), our implementatioll solved the shortest path distance labels in 44.4 seconds and the shortest paths with multiple predecessors in 411.2 seconds. Compared with the 9th DJMACS benchmark solver, our implementation is, respectively, 302.7 times and 32.7 times faster. NETAL succeeded in solving the shortest path distance labels for the USA-road-d.IJSA.gr (ii =24M, m =581V1) without preprocessing in 7.75 days. Numerical results showed that our implementation performance was 432.4 times that of the Δ-stepping algorithm and 228.9 times that of the 9th DIMACS benchmark solver. Furthermore, while GraphCT took 18 hours to compute the betweenness of web-BerkStan, our implementation computed multiple centrality metncs (closeness, graph, stress, and betweenness) simultaneously within 1 hour. A performance increase of 2.4-3.7 times compared with R-MAT graph was confirmed for SSCA#2. © The Operations Research Society of Japan.

DOI： 10.15807/jorsj.54.259

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Mixed polynomial matrices are polynomial matrices with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The computation of their maximum degrees of minors is known to be reducible to valuated independent assignment problems, which can be solved by polynomial numbers of additions, subtractions, and multiplications of rational functions. However, these arithmetic operations on rational functions are much more expensive than those on constants.
In this paper, we present a new algorithm of combinatorial relaxation type. The algorithm finds a combinatorial estimate of the maximum degree by solving a weighted bipartite matching problem, and checks if the estimate is equal to the true value by solving independent matching problems. The algorithm mainly relies on fast combinatorial algorithms and performs numerical computation only when necessary. In addition, it requires no arithmetic operations on rational functions. As a byproduct, this method yields a new algorithm for solving a linear valuated independent assignment problem.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

A mixed matrix pencil is a matrix pencil with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. In this paper, the indices of nilpotency of the Kronecker canonical form for a mixed matrix pencil are characterized in terms of matroids. As a byproduct, this provides an algorithm for computing the rank of a power product of a square mixed matrix.

DOI： 10.1137/100783315

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：JOHN WILEY & SONS LTD  

Modern modeling approaches in circuit simulation naturally lead to differential algebraic equations (DAEs). The index of a DAE is a measure of the degree of numerical difficulty. In general, the higher the index, the more difficult it is to solve the DAE. The modified nodal analysis (MNA) is known to yield a DAE with index at most two in a wide class of nonlinear time-varying electric circuits.
In this paper, we consider a broader class of analysis method called the hybrid analysis. For linear time-invariant RLC circuits, we prove that the index of the DAE arising from the hybrid analysis is at most one, and give a structural characterization for the index of a DAE in the hybrid analysis. This yields an efficient algorithm for finding an optimal hybrid analysis in which the index of the DAE to be solved attains zero. Finally, for linear time-invariant electric circuits that may contain dependent sources, we prove that the optimal hybrid analysis by no means results in a higher index DAE than MNA. Copyright (C) 2008 John Wiley & Sons, Ltd.

DOI： 10.1002/cta.577

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

Modern modeling approaches for circuit analysis lead to differential-algebraic equations (DAEs). The index of a DAE is a measure of the degree of numerical difficulty. In general, the higher the index is, the more difficult it is to solve the DAE. The index of the DAE arising from the modified nodal analysis (MNA) is determined uniquely by the structure of the circuit. Instead, we consider a broader class of analysis method called the hybrid analysis. For linear time-invariant electric circuits, we devise a combinatorial algorithm for finding an optimal hybrid analysis in which the index of the DAE to be solved attains the minimum. The optimal hybrid analysis often results in a DAE with lower index than MNA.

DOI： 10.1007/s10107-008-0227-8

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Commercial packages for transient circuit simulation are often based on the modified nodal analysis (MNA) which allows an automatic setup of model equations and requires a nearly minimal number of variables. However, it may lead to differential-algebraic equations (DAEs) with higher index. Here, we present a hybrid analysis for nonlinear time-varying circuits leading to DAEs with index at most one. This hybrid analysis is based merely on the network topology, which possibly leads to an automatic setup of the hybrid equations from netlists. Moreover, we prove that the minimum index of the DAE arising from the hybrid analysis never exceeds the index from MNA. As a positive side effect, the number of equations from the hybrid analysis is always no greater than that one from MNA. This suggests that the hybrid analysis is superior to MNA in numerical accuracy and computational effort.

DOI： 10.1007/978-3-642-12294-1_20

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

A mixed polynomial matrix is a polynomial matrix which has two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. This paper presents an algorithm for computing the degrees of all cofactors simultaneously in a regular mixed polynomial matrix. The algorithm is based on the valuated matroid intersection and all pair shortest paths. The technique is also used for improving the running time of the algorithm for minimizing the index of the differential-algebraic equation in the hybrid analysis for circuit simulation. © 2009 Society for Industrial and Applied Mathematics.

DOI： 10.1137/070706021

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

A mixed polynomial matrix is a polynomial matrix which has two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. This paper presents an algorithm for computing the degrees of all cofactors simultaneously in a regular mixed polynomial matrix. The algorithm is based on the valuated matroid intersection and all pair shortest paths. The technique is also used for improving the running time of the algorithm for minimizing the index of the differential-algebraic equation in the hybrid analysis for circuit simulation.

DOI： 10.1137/070706021

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE INC  

Differential-algebraic equations (DAEs) naturally arise in many applications, but present numerical and analytical difficulties. The index of a DAE is a measure of the degree of numerical difficulty. In general, the higher the index is, the more difficult it is to solve the DAE. Therefore, it is desirable to transform the original DAE into an equivalent DAE with lower index.
In this paper, we propose an index reduction method for linear DAEs with constant coefficients. The method is applicable to any DAE having at most one derivative per equality. In contrast to the other existing methods, it does not introduce any additional variables. Exploiting a combinatorial property of degrees of minors in polynomial matrices, we show that the method always reduces the index exactly by one. Thus the paper exhibits an application of combinatorial matrix theory to numerical analysis of DAEs. (C) 2008 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.laa.2008.06.025

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)   Publisher：電子情報通信学会  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：計測自動制御学会  

CiNii Books

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Poster presentation  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap