researchmap

researchmap

researchmap

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、理化学研究所（理研）、株式会社フィックスターズ、富士通株式会社による共同研究グループは、 スーパーコンピュータ「富岳」のフルスペックを用いた測定結果で、大規模グラフ解析に関するスーパーコンピュータの国際的な性能ランキングである 「Graph500」における性能向上に成功し、世界第1位を2022年6月に続いて6期連続で獲得しました。

researchmap

researchmap

researchmap

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、理化学研究所（理研）、株式会社フィックスターズ、富士通株式会社による共同研究グループは、 スーパーコンピュータ「富岳」のフルスペックを用いた測定結果で、大規模グラフ解析に関するスーパーコンピュータの国際的な性能ランキングである 「Graph500」における性能向上に成功し、世界第1位を2021年6月に続いて4期連続で獲得しました。
このランキングは、HPC（ハイパフォーマンス・コンピューティング：高性能計算技術）に関する国際会議「SC21」の開催に合わせて、Graph500 Committee から11月15日（日本時間11月16日）に発表されました。
大規模グラフ解析の性能は、大規模かつ複雑なデータ処理が求められるビッグデータの解析において重要な指標となるものであり、世界最高性能を達成した技 術を用いて、民間企業とのアプリケーション開発（スマート工場, MaaS (配送最適化)等)を推進しております。

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、東京工業大学、理化学研究所、スペインの
バルセロナ・ スーパーコンピューティング・センター、富士通株式会社、株式会社フィックスターズによ
る国際共同研究グループは、2019年6月18日（国際会議 ISC2019, ドイツ, フランクフルト)に公開された
最新のビッグデータ処理（大規模グラフ解析）に関するスーパーコンピュータの国際的な性能ランキング
であるGraph500において、スーパーコンピュータ「京（けい）」による解析結果で、2018年11月に続き
9期連続（通算10期）で第1位を獲得した。

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、東京工業大学、理化学研究所、スペインのバルセロナ・ スーパーコンピューティング・センター、富士通株式会社、株式会社フィックスターズによる国際共同研究グループは、2018年11月13日（国際会議 SC18, アメリカ, ダラス)に公開された最新のビッグデータ処理（大規模グラフ解析）に関するスーパーコンピュータの国際的な性能ランキングであるGraph500において、スーパーコンピュータ「京（けい）」による解析結果で、2018年6月に続き8期連続（通算9期）で第1位を獲得しました。

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、東京工業大学、理化学研究所、スペインのバルセロナ・ スーパーコンピューティング・センター、富士通株式会社、株式会社フィックスターズによる国際共同研究グループは、2018年6月27日（国際会議 ISC18, ドイツ, フランクフルト)に公開された最新のビッグデータ処理（大規模グラフ解析）に関するスーパーコンピュータの国際的な性能ランキングであるGraph500において、スーパーコンピュータ「京（けい）」による解析結果で、2017年11月に続き7期連続（通算8期）で第1位を獲得しました。

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、東京工業大学、理化学研究所、スペインのバルセロナ・ スーパーコンピューティング・センター、富士通株式会社、株式会社フィックスターズによる国際共同研究グループは、2017年11月16日（国際会議 SC17, アメリカ, デンバー)に公開された最新のビッグデータ処理（大規模グラフ解析）に関するスーパーコンピュータの国際的な性能ランキングであるGraph500において、スーパーコンピュータ「京（けい）」による解析結果で、2017年6月に続き6期連続（通算7期）で第1位を獲得しました。

九州大学マス・フォア・インダストリ研究所の藤澤克樹教授、東京工業大学、理化学研究所、スペインのバルセロナ・スーパーコンピューティング・センター、富士通株式会社、株式会社フィックスターズによる国際共同研究グループは、2017年6月21日（現地時間）に公開された最新のビッグデータ処理（大規模グラフ解析）に関するスーパーコンピュータの国際的な性能ランキングであるGraph500において、スーパーコンピュータ「京（けい）」による解析結果で、2016年11月に続き5期連続（通算6期）で第1位を獲得しました。

実社会で要求されるグラフ解析などの大規模最適化問題を解決するためには、短時間に膨大な計算量とデータ量を処理するための新技術が必要となる。特に発生後に早急な解決 が望まれる現実問題においては、計算量やデータ量などの規模が大きく従来の手法では処 理が困難である。
本研究では、最先端理論(Algorithm Theory)+ 大規模実データ(BigData)+ 最新 計算技術(Computation)の有機的な組合せによって、スーパーコンピュータ上での並列 数の爆発的増大や記憶装置の多階層化、さらに計算量とデータ移動量の正確な推定による 性能最適化及び省電力計算の実現などの課題に取り組んだ。
本研究により、今後予想され得る実データの大規模化及び複雑化に対処可能となり、さ らに世界最高レベルの性能を持つグラフ探索及び最適化ソフトウェアの開発に成功した. (Graph500 ベンチマーク4期連続(通算5期)世界第 1 位など )。
本成果は、大規模データに対するリアルタイム処理などを活用して、オープンデータやセンサーデータを活用した都市機能の最適化などの実社会への応用などに寄与することが期待される。

九州大学マス・フォア・インダストリ研究所の藤澤 克樹教授、東京工業大学、バルセロナスーパーコンピュータセンター、富士通株式会社、理化学研究所らの共同研究チームは、大規模なグラフを処理するソフトウェアを独自に開発し、京など様々なスーパーコンピュータ上でビッグデータ処理性能を計測するGraph500ベンチマークテストを実施した結果、4期連続で世界第1位となったことが、アメリカのソルトレイクシティで開催されたスーパーコンピュータの国際会議「SC16」で2016年11月15日（日本時間11月16日）に発表されました。

九州大学マス・フォア・インダストリ研究所の藤澤 克樹 教授、東京工業大学、バルセロナスーパーコンピュータセンター、富士通株式会社、理化学研究所らの共同研究チームは、大規模なグラフを処理するソフトウェアを独自に開発し、京など様々なスーパーコンピュータ上でビッグデータ処理性能を計測するGraph500ベンチマークテストを実施した結果、3期連続で世界第1位となったことが、ドイツのフランクフルトで開催されたスーパーコンピュータの国際会議「ISC16」で2016年6月20日（日本時間6月21日）に発表されました。

Graph500と Green Graph500は並行探索,最短路探索をはじめとする最適化,極大独立集合などのグラフ解析,などの複数のグラフ処理カーネルからなるベンチマークにより計算機の性能を評価しランキングを行う.グラフ解析はサイバーセキュリティ,創薬,データマイニング,ネットワーク解析などの分野において必要とされる重要な計算カーネルとして位置づけられている. 我々の研究チームは ISC14にて発表された第８回 Graph500 及び 第３回 Green Graph500 において世界１位の性能を達成した

researchmap

Language：Others   Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

The security of lattice-based cryptography relies on the hardness of solving lattice problems. Lattice basis reduction is a strong tool for solving lattice problems, and the block Korkine–Zolotarev (BKZ) reduction algorithm is the de facto standard in cryptanalysis. We propose a parallel algorithm of BKZ-type reduction based on randomization. Randomized copies of an input lattice basis are independently reduced in parallel, while several basis vectors are shared asynchronously among all processes. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes might work on the same problem, which diminishes the benefit of parallelization. To monitor the balance between randomness and sharing, we propose a new metric to quantify the variety of lattice bases, and we empirically find an optimal parameter of sharing for high-dimensional lattices. We also demonstrate the effectiveness of our parallel algorithm and metric through experiments from multiple perspectives.

DOI： 10.1007/s13160-023-00580-z

Web of Science

Scopus

researchmap

Other Link： https://link.springer.com/article/10.1007/s13160-023-00580-z/fulltext.html

Language：English  

DOI： 10.1016/j.ophtha.2022.10.034

Web of Science

PubMed

Language：Others   Publishing type：Research paper (other academic)   Publisher：IEEE  

Graph embedding is the process of obtaining a vector representation of graph nodes. The representation obtained by graph embedding is highly versatile. It can be used for various tasks, such as recommendation and clustering tasks. However, there are only a few methods that incorporate attributes indicating node characteristics, such as user gender, age, or product category, into graph embedding. Therefore, we hypothesize that nodes with the same attribute are often connected to the same node. Consequently, we propose two methods for graph embedding, parallel and serial, that use metric learning to reflect attribute data in node features. The proposed method can be applied to any graph embedding and metric learning method, and thus can also be applied to many new methods yet to be developed. Numerical experimental results show that the proposed method using node attributes is superior to the existing methods in both AUROC and accuracy.

DOI： 10.1109/BigData55660.2022.10020868

Scopus

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/bigdataconf/bigdataconf2022.html#FujiiTYHKNIHF22

Language：Others   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

The learning with errors (LWE) problem is one of the hard problems assuring the security of modern lattice-based cryptography. Kannan's embedding can reduce Search-LWE, the search version of LWE, to a specific case of the shortest vector problem (SVP). Lattice basis reduction is a powerful instrument for solving lattice problems including SVP. We propose a new way for efficiently solving Search-LWE. While a whole basis is reduced in a standard way, ours reduces only a projected basis. To realize our strategy, we also provide an algorithm for reducing projected bases, based on DeepBKZ that is an enhancement of the block Korkine–Zolotarev (BKZ) algorithm. Moreover, we show implementation results for solving some instances within the Darmstadt LWE challenge.

DOI： 10.1016/j.dam.2022.04.018

Web of Science

Scopus

researchmap

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

DOI： 10.48550/arXiv.2206.09628

Language：Others   Publishing type：Research paper (other academic)  

Diversified Adversarial Attacks based on Conjugate Gradient Method.
Deep learning models are vulnerable to adversarial examples, and adversarial
attacks used to generate such examples have attracted considerable research
interest. Although existing methods based on the steepest descent have achieved
high attack success rates, ill-conditioned problems occasionally reduce their
performance. To address this limitation, we utilize the conjugate gradient (CG)
method, which is effective for this type of problem, and propose a novel attack
algorithm inspired by the CG method, named the Auto Conjugate Gradient (ACG)
attack. The results of large-scale evaluation experiments conducted on the
latest robust models show that, for most models, ACG was able to find more
adversarial examples with fewer iterations than the existing SOTA algorithm
Auto-PGD (APGD). We investigated the difference in search performance between
ACG and APGD in terms of diversification and intensification, and define a
measure called Diversity Index (DI) to quantify the degree of diversity. From
the analysis of the diversity using this index, we show that the more diverse
search of the proposed method remarkably improves its attack success rate.

DOI： 10.48550/arXiv.2206.09628

Language：English   Publisher：Institute of Electrical and Electronics Engineers :IEEE  

Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for postquantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. CMAP-LAP facilitates the implementation of large-scale parallel strategies for lattice problems since all the functions are designed to be customizable and abstract. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.

CiNii Research

Language：English  

DOI： 10.1159/000524558

Web of Science

PubMed

Publisher：Proceedings of Machine Learning Research  

Deep learning models are vulnerable to adversarial examples, and adversarial attacks used to generate such examples have attracted considerable research interest. Although existing methods based on the steepest descent have achieved high attack success rates, ill-conditioned problems occasionally reduce their performance. To address this limitation, we utilize the conjugate gradient (CG) method, which is effective for this type of problem, and propose a novel attack algorithm inspired by the CG method, named the Auto Conjugate Gradient (ACG) attack. The results of large-scale evaluation experiments conducted on the latest robust models show that, for most models, ACG was able to find more adversarial examples with fewer iterations than the existing SOTA algorithm Auto-PGD (APGD). We investigated the difference in search performance between ACG and APGD in terms of diversification and intensification, and define a measure called Diversity Index (DI) to quantify the degree of diversity. From the analysis of the diversity using this index, we show that the more diverse search of the proposed method remarkably improves its attack success rate.

Scopus

Language：English   Publishing type：Research paper (other academic)  

Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us 10 develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. CMAP-LAP facilitates the implementation of large-scale parallel strategies for lattice problems since all the functions are designed to he customizable and abstract. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.

DOI： 10.1109/hipc53243.2021.00018

Repository Public URL： http://hdl.handle.net/2324/4771873

Language：English   Publishing type：Research paper (other academic)  

Internet-Wide Scanner Fingerprint Identifier Based on TCP/IP Header
Identifying individual scan activities is a crucial and challenging activity for mitigating emerging cyber threats or gaining insights into security scans. Sophisticated adversaries distribute their scans over multiple hosts and operate with stealth; therefore, low-rate scans hide beneath other benign traffic. Although previous studies attempted to discover such stealth scans by observing the distribution of ports and hosts, well-organized scans are difficult to find. However, a scanner can embed a fingerprint into the packet fields to distinguish between the scan and other traffic. In this study, we propose a new algorithm to identify the flexible fingerprint in consideration of the genetic algorithm idea. To the best of our knowledge, this is the first such attempt. We successfully identified previously unknown fingerprints rather than existing ones through numerical experiments on darknet traffic. We analyzed the packets and discovered distinctive scan activities. Further, we collated the results with both cyber threat intelligence and investigation/largescale scanner lists to ascertain the reliability of our model.

DOI： 10.1109/FMEC54266.2021.9732414

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

In the daily operation of liquefied petroleum gas service, gas providers
visit customers and replace cylinders if the gas is about to run out. For a
long time, frequent visits to customers were required because they could not
determine the amount of remaining gas without a staff visit and observation. To
solve this problem, smart meters are started to be employed to acquire gas
consumption more frequently without visiting customers. In this study, we
construct a system to optimize plans for cylinder replacement, and evaluate it
with a large-scale field test. We propose an algorithm to create a replacement
plan with three steps: estimating the replacement date, acquiring the customer
list for replacement, and determining the delivery route. A more accurate
estimation of the replacement date can be acquired with a smart meter, which is
used for making a customer list for replacement. The formulation for making a
customer list enables the gas provider to replace cylinders some days before
the date when the gas would run out. It can suppress the concentration of
replacements on certain days. Large-scale verification experiments were
performed with more than 1,000 customers in Chiba prefecture in Japan. In the
field test, the gas provider incorporated the system into its replacement
operations. Moreover, the replacement plans developed by the proposed system
were compared with that by the gas provider. Our system reduced the number of
gas cylinders with gas shortage, the number of visits without replacement due
to plenty of gas remaining, and the working duration per customer, which shows
that our system benefits both gas providers and customers.

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

Map matching is an essential preprocessing step for most trajectory-based intelligent transport system services. Due to device capability constraints and the lack of a high-performance model, map matching for low-sampling-rate trajectories is of particular interest. Therefore, we developed a time-expanded graph matching (TEG-matching) that has three advantages (1) high speed and accuracy, as it is robust for spatial measurement error and a pause such as at traffic lights; (2) being parameter-free, that is, our algorithm has no predetermined hyperparameters; and (3) only requiring ordered locations for map matching. Given a set of low-frequency GPS data, we construct a time-expanded graph (TEG) whose path from source to sink represents a candidate route. We find the shortest path on TEG to obtain the matching route with a small area between the vehicle trajectory. Additionally, we introduce two general speedup techniques (most map matching methods can apply) bottom-up segmentation and fractional cascading. Numerical experiments with worldwide vehicle trajectories in a public dataset show that TEG-matching outperforms state-of-the-art algorithms in terms of accuracy and speed, and we verify the effectiveness of the two general speedup techniques.

DOI： 10.1016/j.trc.2021.103265

Repository Public URL： http://hdl.handle.net/2324/4771850

Language：Others   Publishing type：Research paper (other academic)  

In this paper, we present the performance of the supercomputer Fugaku for breadth-first search (BFS) problem in the Graph500 benchmark, which is known as a ranking benchmark used to evaluate large-scale graph processing performance on supercomputer systems. Fugaku is a huge-scale Japanese exascale supercomputer that consists of 158,976 nodes connected by the Tofu interconnect D (TofuD). We have developed a BFS implementation that can extract the performance of Fugaku. We also optimize the number of processes per node, one-to-one communication, performance power ratio, and process mapping in the six-dimensional mesh/torus topology of TofuD. We evaluate the BFS performance for a large-scale graph consisting of about 2.2 trillion vertices and 35.2 trillion edges using the whole Fugaku system, and achieve 102,956 giga-traversed edges per second (GTEPS), resulting in the first position of Graph500 BFS ranking in November 2020. This performance is 3.3 times higher than that of Fugaku’s previous system, the K computer.

DOI： 10.1007/978-3-030-78713-4_20

Repository Public URL： http://hdl.handle.net/2324/4771851

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

Obstacle Avoidable G2-continuous Trajectory Generated with Clothoid Spline Solution
This research engages in generating trajectories with continuous curvature and applying blending cases. Clothoid spline has an important property that its curvature is linear related to its arclength, this property can provide a curvature (G2) continuity to the interpolation operation. But it is rarely used in the trajectory plan because its shape is hard to control to avoid obstacles. This paper uses a collision-free corridor to limit the trajectory generation to avoid obstacles. In a transformable system, using line segments to connect with Clothoid spiral segments, the computation complexity could be greatly reduced by setting the starting conditions equal to zero. With the computation, a unique solution to the spiral segment is found. The computation process and the corresponding algorithm are elaborated in this paper.

DOI： 10.1109/ICCRE51898.2021.9435729

Language：English   Publishing type：Research paper (other academic)  

This paper introduces a scheme of B-spline calculation, which is used for G2 continuous trajectory generation. The B-spline is composed of line segments, Euler spirals, and arcs. By simplifying and digging in the qualities of Euler spirals, we discover a valid spiral segment criterion. This criterion can be used in deciding how to compose the B-spline. One main trait of the trajectory is that this B-spline trajectory is assumed and generated inside a collision-free corridor in every interpolation scenario. Hence, the trajectory can be G2 continuous and avoid instant obstacles in every scenario case.

DOI： 10.1109/ACIRS52449.2021.9519319

Language：English   Publishing type：Research paper (other academic)  

An automatic and intelligent abnormal electrical process detection scheme is crucial for protecting the stability and power quality of an electrical power system and further, the operation of the future grid. This paper introduces the automatic monitoring system for electrified railway power system and designs a framework based on the convolution neural network for abnormal electrical process detection, integrating the data processing, feature extraction, and classification into one model. Then inception blocks are introduced as a kernel-wise approach to boost the performance. The data from the railway electrification system is applied to this scheme and receives a high performance of 97% abnormal electrical process recognition rate.

DOI： 10.1109/ICMRE51691.2021.9384838

Language：English   Publishing type：Research paper (other academic)  

Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world's first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.

DOI： 10.1109/SC41405.2020.00064

Repository Public URL： http://hdl.handle.net/2324/4771852

Language：Others   Publishing type：Research paper (other academic)  

© 2020 IEEE. There is increasing demand for the high-speed processing of large-scale graphs in various fields. However, such graph processing requires irregular calculations, making it difficult to scale performance on large-scale distributed memory systems. Against this background, Graph500, a competition for evaluating the performance of large-scale graph processing, has been held. We developed breadth-first search (BFS), which is one of the benchmark kernels used in Graph500, and took the top spot a total of 10 times using the K computer. In this paper, we tune BFS performance and evaluate it using the supercomputer Fugaku, which is the successor to the K computer. The results of evaluating BFS for a large-scale graph composed of about 1.1 trillion vertices and 17.6 trillion edges using 92,160 nodes of Fugaku indicate that Fugaku has 2.27 times the performance of the K computer. Fugaku took the top spot on Graph500 in June 2020.

DOI： 10.1109/CLUSTER49012.2020.00053

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

Nested Subspace Arrangement for Representation of Relational Data
Studies on acquiring appropriate continuous representations of discrete
objects, such as graphs and knowledge base data, have been conducted by many
researchers in the field of machine learning. In this study, we introduce
Nested SubSpace (NSS) arrangement, a comprehensive framework for representation
learning. We show that existing embedding techniques can be regarded as special
cases of the NSS arrangement. Based on the concept of the NSS arrangement, we
implement a Disk-ANChor ARrangement (DANCAR), a representation learning method
specialized to reproducing general graphs. Numerical experiments have shown
that DANCAR has successfully embedded WordNet in ${mathbb R}^{20}$ with an F1
score of 0.993 in the reconstruction task. DANCAR is also suitable for
visualization in understanding the characteristics of graphs.

Repository Public URL： http://hdl.handle.net/2324/4485645

Language：English   Publishing type：Research paper (other academic)  

© 2020 IEEE. This paper works on the problem of generating a trajectory which is capable to dodge potential obstacles in a blending occasion with a non-holonomic premise. To the problem, this paper offers a solution of a circular blending curve generation with given directions, lanes and obstacle. This technique reforms the two-dimensional information into one-dimensional representation. With this trait, the obstacles could be represented by the constraints generated with the technique. Then, a collision-free corridor could be formed by the constraints. The corridor generating algorithm can provide outcome at a high speed, also cater to one all multiple obstacles situation.

DOI： 10.1109/ICCRE49379.2020.9096450

Language：Others   Publishing type：Research paper (other academic)  

© 2021, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. The learning with errors (LWE) problem assures the security of modern lattice-based cryptosystems. It can be reduced to classical lattice problems such as the shortest vector problem (SVP) and the closest vector problem (CVP). In particular, the search-LWE problem is reduced to a particular case of SVP by Kannan’s embedding technique. Lattice basis reduction is a mandatory tool to solve lattice problems. In this paper, we give a new strategy to solve the search-LWE problem by lattice reduction over projected bases. Compared with a conventional method of reducing a whole lattice basis, our strategy reduces only a part of the basis and, hence, it gives a practical speed-up in solving the problem. We also develop a reduction algorithm for a projected basis, and apply it to solving several instances in the LWE challenge, which has been initiated since the middle of 2016 in order to assess the hardness of the LWE problem.

DOI： 10.1007/978-981-15-8061-1_3

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

New Performance Index "Attractiveness Factor" for Evaluating Websites via Obtaining Transition of Users' Interests.
© 2019, The Author(s). The studies of browsing behavior have gained increasing attention in web analysis for providing better service. Most of the conventional approaches focus on simple indices such as average dwell time and conversion rate. These indices make similar evaluations to websites even if their features are significantly different. Moreover, such statistical indices are not sensitive to the dynamics of users’ interests. In this paper, we propose a new framework for measuring a website’s attractiveness that takes into account both the distribution and dynamics of users’ interests. Within the framework, we define a new index for the website, called Attractiveness Factor, which evaluates the degree of users’ attention. It consists of three procedures: First, we capture the transition of users’ interests during browsing by solving a nonnegative matrix factorization and constrained network flow problems. To accommodate multiple types of interests of a user, we applied a soft clustering as opposed to a hard clustering to model attributes of users and websites. Second, for each website, the feature of each cluster is obtained by fitting the dwell time distribution with Weibull distribution. Finally, we calculate Attractiveness Factor of a website by applying the results of clustering and fitting. Attractiveness Factor depends on the distribution of the dwell time of users interested in the website, which reflects the change of interest of users. Numerical experiments with real web access data of Yahoo Japan News are conducted by solving extremely large-scale optimization problems. They show that Attractiveness Factor captures more exceptional information about browsing behavior more effectively than well-used indices. Attractive factors give low ratings to category pages; however, it can assign high ratings to websites that attract many people, such as hot topic news about the 2018 FIFA World Cup, Japan’s new imperial era’ REIWA,’ and North Korea—the United States Hanoi Summit. Moreover, we demonstrate that Attractiveness Factor can detect the tendency of users’ attention to each website at a given time interval of the day.

DOI： 10.1007/s41019-019-00112-1

Language：English   Publishing type：Research paper (other academic)  

One of the most critical problems in bike-sharing services is a bicycle repositioning problem, which is how service providers must relocate their bicycles to maintain the quality of service. In this paper, we propose an end-to-end approach for the bike repositioning problem, which realizes the operator-feasible repositioning plan with cooperation among multiple trucks. Our proposed algorithm consists of three procedures. First, we predict the number of rented and returned bicycles at each station with a deep learning based on the bicycle usage information. Second, we determine the optimal number of bicycles to satisfy the availability of each station by solving an integer optimization problem. Finally, we solve the vehicle routing problem formulated as another integer optimization problem. Based on our algorithm, service operators can actually perform a relocation task based with a reference to the truck capacity, routes, and the number of bicycles to be loaded and unloaded. We demonstrate the applicability of our algorithm in the real world through numerical experiments on the real bicycle data of a Japanese company.

DOI： 10.1109/BigData47090.2019.9005986

Language：English   Publishing type：Research paper (other academic)  

One of the most critical problems in bike-sharing services is a bicycle repositioning problem, which is how service providers must relocate their bicycles to maintain the quality of service. In this paper, we propose an end-to-end approach for the bike repositioning problem, which realizes the operatorfeasible repositioning plan with cooperation among multiple trucks. Our proposed algorithm consists of three procedures. First, we predict the number of rented and returned bicycles at each station with a deep learning based on the bicycle usage information. Second, we determine the optimal number of bicycles to satisfy the availability of each station by solving an integer optimization problem. Finally, we solve the vehicle routing problem formulated as another integer optimization problem. Based on our algorithm, service operators can actually perform a relocation task based with a reference to the truck capacity, routes, and the number of bicycles to be loaded and unloaded. We demonstrate the applicability of our algorithm in the real world through numerical experiments on the real bicycle data of a Japanese company.

DOI： 10.1109/BigData47090.2019.9005986

Language：English   Publishing type：Research paper (other academic)  

Cyber-Physical Systems (CPSs) are attracting significant attention from a number of industries, including social infrastructure, manufacturing, retail, among others. We can easily gather big datasets of people and transportation movements by utilizing camera and sensor technologies, and create new industrial applications by optimizing and simulating social mobility in the cyberspace. In this paper, we develop the system which automatically performs a series of processes, including object detection, multiple object tracking, and mobility optimization. The mobility of humans and objects is one of the essential components in the real world. Therefore, our system can be widely applied to various application fields. Our major contributions to this paper are remarkable performance improvement of multiple object tracking and building the new mobility optimization engine. In the former, we improve the multiple object tracker using K-Shortest Paths (KSP), which achieves significant data reduction and acceleration by specifying and deleting unnecessary nodes. Numerical experiments show that our proposed tracker is over three times faster than the original KSP tracker while keeping the accuracy. We formulate the mobility optimization problem as the SATisfiability problem (SAT) and the Integer Programming problem (IP) in the latter. Numerical experiments demonstrate that the total transit time can be reduced from 30 s to 10 s. We discuss the characteristics of solutions obtained by the two formulations. We can finally select the appropriate optimization method according to the constraints of calculation time and accuracy for real applications.

DOI： 10.1109/BigData.2018.8622146

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

The studies of browsing behavior have gained increasing attention in web analysis for providing better service. Most of the conventional approaches focus on simple indices such as average dwell time and conversion rate. These indices make similar evaluations to websites even if their features are significantly different. Moreover, such statistical indices are not sensitive to the dynamics of users’ interests. In this paper, we propose a new framework for measuring a website’s attractiveness that takes into account both the distribution and dynamics of users’ interests. Within the framework, we define a new index for the website, called Attractiveness Factor, which evaluates the degree of users’ attention. It consists of three procedures: First, we capture the transition of users’ interests during browsing by solving a nonnegative matrix factorization and constrained network flow problems. To accommodate multiple types of interests of a user, we applied a soft clustering as opposed to a hard clustering to model attributes of users and websites. Second, for each website, the feature of each cluster is obtained by fitting the dwell time distribution with Weibull distribution. Finally, we calculate Attractiveness Factor of a website by applying the results of clustering and fitting. Attractiveness Factor depends on the distribution of the dwell time of users interested in the website, which reflects the change of interest of users. Numerical experiments with real web access data of Yahoo Japan News are conducted by solving extremely large-scale optimization problems. They show that Attractiveness Factor captures more exceptional information about browsing behavior more effectively than well-used indices. Attractive factors give low ratings to category pages; however, it can assign high ratings to websites that attract many people, such as hot topic news about the 2018 FIFA World Cup, Japan’s new imperial era’ REIWA,’ and North Korea—the United States Hanoi Summit. Moreover, we demonstrate that Attractiveness Factor can detect the tendency of users’ attention to each website at a given time interval of the day.

DOI： 10.1007/s41019-019-00112-1

Language：English  

In this paper, we present our ongoing research project. The objective of many ongoing research projects in high-performance computing (HPC) areas is to develop an advanced computing and optimization infrastructure for extremely largescale graphs on the peta-scale supercomputers. The extremely large-scale graphs that have recently emerged in various application fields, such as transportation, social networks, cybersecurity, disaster prevention, and bioinformatics, require fast and scalable analysis. The Graph500 benchmark measures the performance of any supercomputer performing a breadth-first search (BFS) in terms of traversed edges per second (TEPS). In 2014-2017, our project team has achieved about 38.6TeraTEPS on K computer and been a winner at the 8th and 10th to 15th Graph500 benchmark. We commenced our research project for developing the Urban OS (Operating System) for a large-scale city in 2013. The Urban OS, which is regarded as one of the emerging applications of the cyber-physical system (CPS), gathers big data sets of the distribution of people and transportation movements by utilizing sensor technologies and storing them in the cloud storage system. In the next step, we apply optimization, simulation, and deep learning techniques to solve them and check the validity of solutions obtained on the cyberspace. The Urban OS employs the graph analysis system developed by this research project and provides a feedback to a predicting and controlling center to optimize many social systems and services.We briefly explain our ongoing research project for realizing the Urban OS.

DOI： 10.1007/978-981-13-1924-2_11

Language：Others  

© Springer Nature Singapore Pte Ltd. 2019. All rights reserved. In this paper, we present our ongoing research project. The objective of many ongoing research projects in high-performance computing (HPC) areas is to develop an advanced computing and optimization infrastructure for extremely largescale graphs on the peta-scale supercomputers. The extremely large-scale graphs that have recently emerged in various application fields, such as transportation, social networks, cybersecurity, disaster prevention, and bioinformatics, require fast and scalable analysis. The Graph500 benchmark measures the performance of any supercomputer performing a breadth-first search (BFS) in terms of traversed edges per second (TEPS). In 2014-2017, our project team has achieved about 38.6TeraTEPS on K computer and been a winner at the 8th and 10th to 15th Graph500 benchmark. We commenced our research project for developing the Urban OS (Operating System) for a large-scale city in 2013. The Urban OS, which is regarded as one of the emerging applications of the cyber-physical system (CPS), gathers big data sets of the distribution of people and transportation movements by utilizing sensor technologies and storing them in the cloud storage system. In the next step, we apply optimization, simulation, and deep learning techniques to solve them and check the validity of solutions obtained on the cyberspace. The Urban OS employs the graph analysis system developed by this research project and provides a feedback to a predicting and controlling center to optimize many social systems and services.We briefly explain our ongoing research project for realizing the Urban OS.

DOI： 10.1007/978-981-13-1924-2_11

Language：English   Publishing type：Research paper (other academic)  

© 2018 IEEE. Cyber-Physical Systems (CPSs) are attracting significant attention from a number of industries, including social infrastructure, manufacturing, retail, among others. We can easily gather big datasets of people and transportation movements by utilizing camera and sensor technologies, and create new industrial applications by optimizing and simulating social mobility in the cyberspace. In this paper, we develop the system which automatically performs a series of processes, including object detection, multiple object tracking, and mobility optimization. The mobility of humans and objects is one of the essential components in the real world. Therefore, our system can be widely applied to various application fields. Our major contributions to this paper are remarkable performance improvement of multiple object tracking and building the new mobility optimization engine. In the former, we improve the multiple object tracker using K-Shortest Paths (KSP), which achieves significant data reduction and acceleration by specifying and deleting unnecessary nodes. Numerical experiments show that our proposed tracker is over three times faster than the original KSP tracker while keeping the accuracy. We formulate the mobility optimization problem as the SATisfiability problem (SAT) and the Integer Programming problem (IP) in the latter. Numerical experiments demonstrate that the total transit time can be reduced from 30 s to 10 s. We discuss the characteristics of solutions obtained by the two formulations. We can finally select the appropriate optimization method according to the constraints of calculation time and accuracy for real applications.

DOI： 10.1109/BigData.2018.8622146

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

The power consumption of server platforms has been increasing as the amount of hardware resources equipped on them is increased. Especially, the capacity of DRAM continues to grow, and it is not rare that DRAM consumes higher power than processors on modern servers. Therefore, a reduction in the DRAM energy consumption is a critical challenge to reduce the system-level energy consumption. Although it is well known that improving row buffer locality (RBL) and bank-level parallelism (BLP) is effective to reduce the DRAM energy consumption, our preliminary evaluation on a real server demonstrates that RBL is generally low across 15 multithreaded benchmarks. In this paper, we investigate the memory access patterns of these benchmarks using a simulator and observe that cache line-grained channel interleaving schemes, which are widely applied to modern servers including multiple memory channels, hurt the RBL each of the benchmarks potentially possesses. In order to address this problem, we focus on a row-grained channel interleaving scheme and compare it with three cache line-grained schemes. Our evaluation shows that it reduces the DRAM energy consumption by 16.7%, 12.3%, and 5.5%on average (up to 34.7%, 28.2%, and 12.0%) compared to the other schemes, respectively.

DOI： 10.1587/transinf.2017EDP7296

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

© 2018 For hybrid electric vehicle (HEV) systems, studies using model-based simulators have been actively conducted. The vehicle powertrain simulator makes it easier to evaluate the powertrain system. In this paper, we utilize a Toyota Hybrid System (THS) simulator to obtain a long-term control that optimizes the fuel efficiency when the vehicle speed over a certain period is given. Our proposed method obtains optimal long-term control by solving the shortest path problem with state of charge (SOC) constraints after constructing a graph expressing the transition of the fuel and battery consumption. We also propose a search method for vehicle control using bicubic spline interpolation without the preparation of a controller. We finally remove almost all edges from a graph by 97.2% at most through the utilization of 0-1 integer linear programming, which enables a 3.88x speedup in obtaining the optimal vehicle control.

DOI： 10.1016/j.ifacol.2018.10.037

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

© 2018 The Institute of Electronics, Information and Communication Engineers. The power consumption of server platforms has been increasing as the amount of hardware resources equipped on them is increased. Especially, the capacity of DRAM continues to grow, and it is not rare that DRAM consumes higher power than processors on modern servers. Therefore, a reduction in the DRAM energy consumption is a critical challenge to reduce the system-level energy consumption. Although it is well known that improving row buffer locality (RBL) and bank-level parallelism (BLP) is effective to reduce the DRAM energy consumption, our preliminary evaluation on a real server demonstrates that RBL is generally low across 15 multithreaded benchmarks. In this paper, we investigate the memory access patterns of these benchmarks using a simulator and observe that cache line-grained channel interleaving schemes, which are widely applied to modern servers including multiple memory channels, hurt the RBL each of the benchmarks potentially possesses. In order to address this problem, we focus on a row-grained channel interleaving scheme and compare it with three cache line-grained schemes. Our evaluation shows that it reduces the DRAM energy consumption by 16.7%, 12.3%, and 5.5%on average (up to 34.7%, 28.2%, and 12.0%) compared to the other schemes, respectively.

DOI： 10.1587/transinf.2017EDP7296

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

For hybrid electric vehicle (HEV) systems, studies using model-based simulators have been actively conducted. The vehicle powertrain simulator makes it easier to evaluate the powertrain system. In this paper, we utilize a Toyota Hybrid System (THS) simulator to obtain a long-term control that optimizes the fuel efficiency when the vehicle speed over a certain period is given. Our proposed method obtains optimal long-term control by solving the shortest path problem with state of charge (SOC) constraints after constructing a graph expressing the transition of the fuel and battery consumption. We also propose a search method for vehicle control using bicubic spline interpolation without the preparation of a controller. We finally remove almost all edges from a graph by 97.2% at most through the utilization of 0-1 integer linear programming, which enables a 3.88x speedup in obtaining the optimal vehicle control.

DOI： 10.1016/j.ifacol.2018.10.037

Language：English   Publishing type：Research paper (other academic)  

© 2017 IEEE. In this paper, we propose a practical approach to evacuation planning by utilizing network flow and deep learning algorithms. In recent years, large amounts of data are rapidly being stored in the cloud system, and effective data utilization for solving real-world problems is required more than ever. Hierarchical Data Analysis and Optimization System (HDAOS) enables us to select appropriate algorithms according to the degree of difficulty in solving problems and a given time for the decision-making process, and such selection helps address real-world problems. In the field of emergency evacuation planning, however, the Lexicographically Quickest Flow (LQF) algorithm has an extremely long computation time on a large-scale network, and is therefore not a practical solution. For Osaka city, which is the second-largest city in Japan, we must solve the maximum flow problems on a large-scale network with over 8.3M nodes and 32.8M arcs for obtaining an optimal plan. Consequently, we can feed back nothing to make an evacuation plan. To solve the problem, we utilize the optimal solution as training data of a deep Convolutional Neural Network (CNN). We train a CNN by using the results of the LQF algorithm in normal time, and in emergencies predict the evacuation completion time (ECT) immediately by the well-learned CNN. Our approach provides almost precise ECT, achieving an average regression error of about 2%. We provide several techniques for combining LQF with CNN and addressing numerous movements as CNN's input, which has rarely been considered in previous studies. Hodge decomposition also demonstrates that LQF is efficient from the standpoint of the total distance traveled by all evacuees, which reinforces the validity of the method of utilizing the LQF algorithm for deep learning.

DOI： 10.1109/BigData.2017.8258322

Language：English   Publishing type：Research paper (other academic)  

In this paper, we propose a practical approach to evacuation planning by utilizing network flow and deep learning algorithms. In recent years, large amounts of data are rapidly being stored in the cloud system, and effective data utilization for solving real-world problems is required more than ever. Hierarchical Data Analysis and Optimization System (HDAOS) enables us to select appropriate algorithms according to the degree of difficulty in solving problems and a given time for the decision-making process, and such selection helps address real-world problems. In the field of emergency evacuation planning, however, the Lexicographically Quickest Flow (LQF) algorithm has an extremely long computation time on a large-scale network, and is therefore not a practical solution. For Osaka city, which is the second-largest city in Japan, we must solve the maximum flow problems on a large-scale network with over 8.3M nodes and 32.8M arcs for obtaining an optimal plan. Consequently, we can feed back nothing to make an evacuation plan. To solve the problem, we utilize the optimal solution as training data of a deep Convolutional Neural Network (CNN). We train a CNN by using the results of the LQF algorithm in normal time, and in emergencies predict the evacuation completion time (ECT) immediately by the well-learned CNN. Our approach provides almost precise ECT, achieving an average regression error of about 2%. We provide several techniques for combining LQF with CNN and addressing numerous movements as CNN's input, which has rarely been considered in previous studies. Hodge decomposition also demonstrates that LQF is efficient from the standpoint of the total distance traveled by all evacuees, which reinforces the validity of the method of utilizing the LQF algorithm for deep learning.

DOI： 10.1109/BigData.2017.8258322

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

When a massive disaster occurs, to repair the damaged part of lifeline networks, planning is needed to appropriately allocate tasks to two or more restoration teams and optimize their traveling routes. However, precedence and synchronization constraints make restoration teams interdependent of one another, and impede a successful solution by standard local search. In this paper, we propose an indirect local search method using the product set of team-wise permutations as an auxiliary search space. It is shown that our method successfully avoids the interdependence problem induced by the precedence and synchronization constraints, and that it has the big advantage of non-deteriorating perturbations being available for iterated local search.

DOI： 10.1186/s40736-017-0032-5

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

There are many large-scale graphs in real world such as Web graphs and social graphs. The interest in large-scale graph analysis is growing in recent years. Breadth-First Search (BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid BFS algorithm by Beamer (Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, IPDPSW ’13, IEEE Computer Society, Washington, 2013), we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and several optimization techniques such as vertex reordering and load balancing. Our performance evaluation on K-Computer shows that our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously known best techniques.

DOI： 10.1007/s41019-016-0024-y

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

Efficient Breadth-First Search on Massively Parallel and Distributed-Memory Machines
There are many large-scale graphs in real world such as Web graphs and social graphs. The interest in large-scale graph analysis is growing in recent years. Breadth-First Search (BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid BFS algorithm by Beamer (Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, IPDPSW '13, IEEE Computer Society, Washington, 2013), we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and several optimization techniques such as vertex reordering and load balancing. Our performance evaluation on K-Computer shows that our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously known best techniques.

DOI： 10.1007/s41019-016-0024-y

Language：English   Publishing type：Research paper (other academic)  

Graph analysis applications have been widely used in real services such as road-traffic analysis and social network services. Breadth-first search (BFS) is one of the most representative algorithms for such applications; therefore, many researchers have tuned it to maximize performance. On the other hand, owing to the strict power constraints of modern HPC systems, it is necessary to improve power efficiency (i.e., performance per watt) when executing BFS. In this work, we focus on the power efficiency of DRAM and investigate the memory access pattern of a state-of-the-art BFS implementation using a cycle-accurate processor simulator. The results reveal that the conventional address mapping schemes of modern memory controllers do not efficiently exploit row buffers in DRAM. Thus, we propose a new scheme called per-row channel interleaving and improve the DRAM power efficiency by 30.3% compared to a conventional scheme for a certain simulator setting. Moreover, we demonstrate that this proposed scheme is effective for various configurations of memory controllers.

DOI： 10.1109/HPGDMP.2016.010

Language：English   Publishing type：Research paper (other academic)  

The breadth-first search (BFS) is one of the most centric processing in graph theory. In this paper, we presented a fast, scalable, and energy-efficient BFS for a nonuniform memory access (NUMA)-based system, in which the NUMA architecture was carefully considered. Our implementation achieved performance rates of 175 billion edges per second for Kronecker graph with 233 vertices and 237 edges on two racks of a SGI UV 2000 system with 1,280 threads and the fastest entries for a shared-memory system in the June 2014 and November 2014 Graph500 lists. It also produced the most energy-efficient entries in the first and second (small data category) and third, fourth, fifth, and sixth (big data category) Green Graph500 lists on a 4-socket Intel Xeon E5-4640 system.

DOI： 10.1007/978-981-10-0962-4_6

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

Evaluating the impacts of code-level performance tunings on power efficiency.
© 2016 IEEE. As the power consumption of HPC systems will be a primary constraint for exascale computing, a main objective in HPC communities is recently becoming to maximize power efficiency (i.e., performance per watt) rather than performance. Although programmers have spent a considerable effort to improve performance by tuning HPC programs at a code level, tunings for improving power efficiency is now required. In this work, we select two representative HPC programs (Graph500 and SDPARA) and evaluate how traditional code-level performance tunings applied to these programs affect power efficiency. We also investigate the impacts of the tunings on power efficiency at various operating frequencies of CPUs and/or GPUs. The results show that the tunings significantly improve power efficiency, and different types of tunings exhibit different trends in power efficiency by varying CPU frequency. Finally, the scalability and power efficiency of state-of-the-art Graph500 implementations are explored on both a single-node platform and a 960-node supercomputer. With their high scalability, they achieve 27.43 MTEPS/Watt with 129.76 GTEPS on the single-node system and 4.39 MTEPS/Watt with 1,085.24 GTEPS on the supercomputer.

DOI： 10.1109/BigData.2016.7840624

Language：Others   Publishing type：Research paper (other academic)  

Graph analysis applications have been widely used in real services such as road-traffic analysis and social network services. Breadth-first search (BFS) is one of the most representative algorithms for such applications; therefore, many researchers have tuned it to maximize performance. On the other hand, owing to the strict power constraints of modern HPC systems, it is necessary to improve power efficiency (i.e., performance per watt) when executing BFS. In this work, we focus on the power efficiency of DRAM and investigate the memory access pattern of a state-of-the-art BFS implementation using a cycle-accurate processor simulator. The results reveal that the conventional address mapping schemes of modern memory controllers do not efficiently exploit row buffers in DRAM. Thus, we propose a new scheme called per-row channel interleaving and improve the DRAM power efficiency by 30.3% compared to a conventional scheme for a certain simulator setting. Moreover, we demonstrate that this proposed scheme is effective for various configurations of memory controllers.

DOI： 10.1109/HPGDMP.2016.010

Language：English   Publishing type：Research paper (other academic)  

© 2016 IEEE. Breadth-First Search(BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid-BFS algorithm by Beamer[3], we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and optimization techniques such as vertex reordering and load balancing. Performance evaluation on the K shows our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously-known best techniques.

DOI： 10.1109/BigData.2016.7840705

Language：English   Publishing type：Research paper (other academic)  

Breadth-first search (BFS) is one of the most fundamental processing algorithm singraph theory. We previously presented a scalable BFS algorithm based on Beamer's direction optimizing algorithm forn on-uniform memory access(NUMA)-based systems, in which the NUMA architecture was care-fully considered. This paper presents our new implementation that reduces remote memory access in a top-down direction of direction-optimizing algorithm. We also discuss numerical results obtained on the SGI UV 2000 and UV 300 systems, which are shared-memory super computers based on a cache coherent (cc)-NUMA architecture that can handle thousands of threads on a single operating system. Our implementation has a chieved performance rates of 219 billion edges per second on a Kronecker graph with 2(34) vertices and 2(38) edges on arack of an SGI UV 300 system with 1,152 threads. This result exceeds the fast estentry for a shared memory system on the current Graph500 list presented in November 2015, which includes our previous implementation.

DOI： 10.1145/2915516.2915522

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

Language：English   Publishing type：Research paper (other academic)  

Breadth-first search (BFS) is one of the most fundamental processing algorithms in graph theory. We previously presented a scalable BFS algorithm based on Beamer's direction-optimizing algorithm for non-uniform memory access (NUMA)-based systems, in which the NUMA architecture was carefully considered. This paper presents our new implementation that reduces remote memory access in a top-down direction of direction-optimizing algorithm. We also discuss numerical results obtained on the SGI UV 2000 and UV 300 systems, which are shared-memory supercomputers based on a cache coherent (cc)-NUMA architecture that can handle thousands of threads on a single operating system. Our implementation has achieved performance rates of 219 billion edges per second on a Kronecker graph with 2³⁴ vertices and 2³⁸ edges on a rack of an SGI UV 300 system with 1,152 threads. This result exceeds the fastest entry for a shared-memory system on the current Graph500 list presented in November 2015, which includes our previous implementation.

DOI： 10.1145/2915516.2915522

Language：English   Publishing type：Research paper (other academic)  

© Springer International Publishing Switzerland 2016. In this talk, we present our ongoing research project. The objective of this project is to develop advanced computing and optimization infrastructures for extremely large-scale graphs on post petascale supercomputers. We explain our challenge to Graph 500 and Green Graph 500 benchmarks that are designed to measure the performance of a computer system for applications that require irregular memory and network access patterns. The 1st Graph500 list was released in November 2010. The Graph500 benchmark measures the performance of any supercomputer performing a BFS (Breadth-First Search) in terms of traversed edges per second (TEPS). In 2014 and 2015, our project team was a winner of the 8th, 10th, and 11th Graph500 and the 3rd to 6th Green Graph500 benchmarks, respectively. We also present our parallel implementation for large-scale SDP (SemiDefinite Programming) problem. The semidefinite programming (SDP) problem is a predominant problem in mathematical optimization. The primal-dual interior-point method (PDIPM) is one of the most powerful algorithms for solving SDP problems, and many research groups have employed it for developing software packages. We solved the largest SDP problem (which has over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.774 PFlops in double precision for largescale Cholesky factorization using 2,720 CPUs and 4,080 GPUs on the TSUBAME 2.5 supercomputer.

DOI： 10.1007/978-3-319-42432-3_33

Language：English   Publishing type：Research paper (other academic)  

In this talk, we present our ongoing research project. The objective of this project is to develop advanced computing and optimization infrastructures for extremely large-scale graphs on post petascale supercomputers. We explain our challenge to Graph 500 and Green Graph 500 benchmarks that are designed to measure the performance of a computer system for applications that require irregular memory and network access patterns. The 1st Graph500 list was released in November 2010. The Graph500 benchmark measures the performance of any supercomputer performing a BFS (Breadth-First Search) in terms of traversed edges per second (TEPS). In 2014 and 2015, our project team was a winner of the 8th, 10th, and 11th Graph500 and the 3rd to 6th Green Graph500 benchmarks, respectively. We also present our parallel implementation for large-scale SDP (SemiDefinite Programming) problem. The semidefinite programming (SDP) problem is a predominant problem in mathematical optimization. The primal-dual interior-point method (PDIPM) is one of the most powerful algorithms for solving SDP problems, and many research groups have employed it for developing software packages. We solved the largest SDP problem (which has over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.774 PFlops in double precision for largescale Cholesky factorization using 2,720 CPUs and 4,080 GPUs on the TSUBAME 2.5 supercomputer.

DOI： 10.1007/978-3-319-42432-3_33

Language：English   Publishing type：Research paper (other academic)  

Breadth-First Search(BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid-BFS algorithm by Beamer[3], we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and optimization techniques such as vertex reordering and load balancing. Performance evaluation on the K shows our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously-known best techniques.

DOI： 10.1109/BigData.2016.7840705

Language：English   Publishing type：Research paper (other academic)  

As the power consumption of HPC systems will be a primary constraint for exascale computing, a main objective in HPC communities is recently becoming to maximize power efficiency (i.e., performance per watt) rather than performance. Although programmers have spent a considerable effort to improve performance by tuning HPC programs at a code level, tunings for improving power efficiency is now required. In this work, we select two representative HPC programs (Graph500 and SDPARA) and evaluate how traditional code-level performance tunings applied to these programs affect power efficiency. We also investigate the impacts of the tunings on power efficiency at various operating frequencies of CPUs and/or GPUs. The results show that the tunings significantly improve power efficiency, and different types of tunings exhibit different trends in power efficiency by varying CPU frequency. Finally, the scalability and power efficiency of state-of-the-art Graph500 implementations are explored on both a single-node platform and a 960-node supercomputer. With their high scalability, they achieve 27.43 MTEPS/Watt with 129.76 GTEPS on the single-node system and 4.39 MTEPS/Watt with 1,085.24 GTEPS on the supercomputer.

DOI： 10.1109/BigData.2016.7840624

Language：English   Publishing type：Research paper (other academic)  

The Cholesky factorization is an important linear algebra kernel which is used in the semidefinite programming (SDP) problem. However, the large computation costs for Cholesky factorization of the Schur complement matrix (SCM) has been obstacles to solve large scale problems. This paper describes a brand-new version of the parallel SDP solver, SDPARA, which has been equipped with a Cholesky factorization implementation and demonstrated 1.7PFlops performance with over two million constraints by using 4,080 GPUs. The performance and scalability is even more improved by introducing a data-driven approach, rather than traditional synchronous approach. Also we point out that typical data-driven implementations have limitation in scalability, and demonstrate the efficiency of the proposed approach via experiments on TSUBAME2.5 supercomputer.

DOI： 10.1145/2832241.2832245

Language：Others   Publishing type：Research paper (other academic)  

© 2015 ACM. The Cholesky factorization is an important linear algebra kernel which is used in the semidefinite programming (SDP) problem. However, the large computation costs for Cholesky factorization of the Schur complement matrix (SCM) has been obstacles to solve large scale problems. This paper describes a brand-new version of the parallel SDP solver, SDPARA, which has been equipped with a Cholesky factorization implementation and demonstrated 1.7PFlops performance with over two million constraints by using 4,080 GPUs. The performance and scalability is even more improved by introducing a data-driven approach, rather than traditional synchronous approach. Also we point out that typical data-driven implementations have limitation in scalability, and demonstrate the efficiency of the proposed approach via experiments on TSUBAME2.5 supercomputer.

DOI： 10.1145/2832241.2832245

Language：English   Publishing type：Research paper (other academic)  

The breadth-first search (BFS) is one of the most centric kernels in graph processing. Beamer's direction-optimizing BFS algorithm, which selects one of two traversal directions at each level, can reduce unnecessary edge traversals. In a previous paper, we presented an efficient BFS for a non-uniform memory access (NUMA)-based system, in which the NUMA architecture was carefully considered. In this paper, we investigate the locality of memory accesses in terms of the communication with remote memories in a BFS for a NUMA system, and describe a fast and highly scalable implementation. Our new implementation achieves performance rates of 174.704 billion edges per second for a Kronecker graph with 2(33) vertices and 2(37) edges on two racks of a SGI UV 2000 system with 1,280 threads. The implementations described in this paper achieved the fastest entries for a shared-memory system in the June 2014 and November 2014 Graph500 lists, and produced the most energy-efficient entries in the second, third, and fourth Green Graph500 lists (big data category).

DOI： 10.1109/HPCSim.2015.7237065

Language：English  

A Matrix Scheduling Heuristic to Disaster Restoration of Lifeline Networks

Language：English   Publishing type：Research paper (other academic)  

The breadth-first search (BFS) is one of the most centric kernels in graph processing. Beamer's direction-optimizing BFS algorithm, which selects one of two traversal directions at each level, can reduce unnecessary edge traversals. In a previous paper, we presented an efficient BFS for a non-uniform memory access (NUMA)-based system, in which the NUMA architecture was carefully considered. In this paper, we investigate the locality of memory accesses in terms of the communication with remote memories in a BFS for a NUMA system, and describe a fast and highly scalable implementation. Our new implementation achieves performance rates of 174.704 billion edges per second for a Kronecker graph with 2³³ vertices and 2³⁷ edges on two racks of a SGI UV 2000 system with 1,280 threads. The implementations described in this paper achieved the fastest entries for a shared-memory system in the June 2014 and November 2014 Graph500 lists, and produced the most energy-efficient entries in the second, third, and fourth Green Graph500 lists (big data category).

DOI： 10.1109/HPCSim.2015.7237065

Language：English   Publishing type：Research paper (other academic)  

We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 2³¹ vertices and 2³⁵ edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 % performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

DOI： 10.1109/BigData.2014.7004270

Language：English   Publishing type：Research paper (other academic)  

NVM devices will greatly expand the possibility of processing extremely large-scale graphs that exceed the DRAM capacity of the nodes, however, efficient implementation based on detailed performance analysis of access patterns of unstructured graph kernel on systems that utilize a mixture of DRAM and NVM devices has not been well investigated. We introduce a graph data offloading technique using NVMs that augment the hybrid BFS (Breadth-first search) algorithm widely used in the Graph500 benchmark, and conduct performance analysis to demonstrate the utility of NVMs for unstructured data. Experimental results of a Scale27 problem of a Kronecker graph compliant to the Graph500 benchmark show that our approach maximally sustains 4.22 Giga TEPS (Traversed Edges Per Second), reducing DRAM size by half with only 19.18% performance degradation on a 4-way AMD Opteron 6172 machine heavily equipped with NVM devices. Although direct comparison is difficult, this is significantly greater than the result of 0.05 GTEPS for a SCALE 36 problem by using 1TB of DRAM and 12 TB of NVM as reported by Pearce et al. Although our approach uses higher DRAM to NVM ratio, we show that a good compromise is achievable between performance vs. capacity ratio for processing large-scale graphs. This result as well as detailed performance analysis of the proposed technique suggests that we can process extremely large-scale graphs per node with minimum performance degradation by carefully considering the data structures of a given graph and the access patterns to both DRAM and NVM devices. As a result, our implementation has achieved 4.35 MTEPS/W(Mega TEPS per Watt) and ranked 4th on November 2013 edition of the Green Graph500 list in the Big Data category by using only a single fat server heavily equipped with NVMs.

DOI： 10.1109/IPDPSW.2014.189

Language：English   Publishing type：Research paper (other academic)  

© 2014 IEEE. NVM devices will greatly expand the possibility of processing extremely large-scale graphs that exceed the DRAM capacity of the nodes, however, efficient implementation based on detailed performance analysis of access patterns of unstructured graph kernel on systems that utilize a mixture of DRAM and NVM devices has not been well investigated. We introduce a graph data offloading technique using NVMs that augment the hybrid BFS (Breadth-first search) algorithm widely used in the Graph500 benchmark, and conduct performance analysis to demonstrate the utility of NVMs for unstructured data. Experimental results of a Scale27 problem of a Kronecker graph compliant to the Graph500 benchmark show that our approach maximally sustains 4.22 Giga TEPS (Traversed Edges Per Second), reducing DRAM size by half with only 19.18% performance degradation on a 4-way AMD Opteron 6172 machine heavily equipped with NVM devices. Although direct comparison is difficult, this is significantly greater than the result of 0.05 GTEPS for a SCALE 36 problem by using 1TB of DRAM and 12 TB of NVM as reported by Pearce et al. Although our approach uses higher DRAM to NVM ratio, we show that a good compromise is achievable between performance vs. capacity ratio for processing large-scale graphs. This result as well as detailed performance analysis of the proposed technique suggests that we can process extremely large-scale graphs per node with minimum performance degradation by carefully considering the data structures of a given graph and the access patterns to both DRAM and NVM devices. As a result, our implementation has achieved 4.35 MTEPS/W(Mega TEPS per Watt) and ranked 4th on November 2013 edition of the Green Graph500 list in the Big Data category by using only a single fat server heavily equipped with NVMs.

DOI： 10.1109/IPDPSW.2014.189

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

In this article we propose a simple heuristic algorithm for approaching the maximally predictable portfolio, which is constructed so that return model of the resulting portfolio would attain the largest goodness-of-fit. It is obtained by solving a fractional program in which a ratio of two convex quadratic functions is maximized, and the number of variables associated with its nonconcavity has been a bottleneck in spite of continuing endeavour for its global optimization. The proposed algorithm can be implemented by simply solving a series of convex quadratic programs, and computational results show that it yields within a few seconds a (near) Karush-Kuhn-Tucker solution to each of the instances which were solved via a global optimization method in [H. Konno, Y. Takaya and R. Yamamoto, A maximal predictability portfolio using dynamic factor selection strategy, Int. J. Theor. Appl. Fin. 13 (2010) pp. 355-366]. In order to confirm the solution accuracy, we also pose a semidefinite programming relaxation approach, which succeeds in ensuring a near global optimality of the proposed approach. Our findings through computational experiments encourage us not to employ the global optimization approach, but to employ the local search algorithm for solving the fractional program of much larger size. © 2014 Taylor & Francis Group, LLC.

DOI： 10.1080/02331934.2012.741237

Language：English  

Language：English  

Language：Others   Publishing type：Research paper (other academic)  

Breadth-first search (BFS) is an important graph analysis kernel. The Graph500 benchmark measures a computer's BFS performance using the traversed edges per second (TEPS) ratio. Our previous nonuniform memory access (NUMA)-optimized BFS reduced memory accesses to remote RAM on a NUMA architecture system; its performance was 11 GTEPS (giga TEPS) on a 4-way Intel Xeon E5-4640 system. Herein, we investigated the computational complexity of the bottom-up, a major bottleneck in NUMA-optimized BFS. We clarify the relationship between vertex out-degree and bottom-up performance. In November 2013, our new implementation achieved a Graph500 benchmark performance of 37.66 GTEPS (fastest for a single node) on an SGI Altix UV1000 (one-rack) and 31.65 GTEPS (fastest for a single server) on a 4-way Intel Xeon E5-4650 system. Furthermore, we achieved the highest Green Graph500 performance of 153.17 MTEPS/W (mega TEPS per watt) on an Xperia-A SO-04E with a Qualcomm Snapdragon S4 Pro APQ8064. © 2014 Springer International Publishing.

DOI： 10.1007/978-3-319-07518-1_23

Language：English  

Language：English   Publishing type：Research paper (other academic)  

The semi definite programming (SDP) problem is one of the central problems in mathematical optimization. The primal-dual interior-point method (PDIPM) is one of the most powerful algorithms for solving SDP problems, and many research groups have employed it for developing software packages. However, two well-known major bottlenecks, i.e., the generation of the Schur complement matrix (SCM) and its Cholesky factorization, exist in the algorithmic framework of the PDIPM. We have developed a new version of the semi definite programming algorithm parallel version (SDPARA), which is a parallel implementation on multiple CPUs and GPUs for solving extremely large-scale SDP problems with over a million constraints. SDPARA can automatically extract the unique characteristics from an SDP problem and identify the bottleneck. When the generation of the SCM becomes a bottleneck, SDPARA can attain high scalability using a large quantity of CPU cores and some processor affinity and memory interleaving techniques. SDPARA can also perform parallel Cholesky factorization using thousands of GPUs and techniques for overlapping computation and communication if an SDP problem has over two million constraints and Cholesky factorization constitutes a bottleneck. We demonstrate that SDPARA is a high-performance general solver for SDPs in various application fields through numerical experiments conducted on the TSUBAME 2.5 supercomputer, and we solved the largest SDP problem (which has over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.713 PFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs. © 2014 IEEE.

DOI： 10.1109/IPDPS.2014.121

Language：English  

最適化問題の高速計算と実社会への応用にも取り組んでおり、例えば半正定値計画問題(SDP)は組合せ最適化, システムと制御, データ科学, 金融工学, 量子化学など非常に幅広い応用を持ち、現在最適化の研究分野で最も注目されている最適化問題の一つとなっている。SDP に対しては高速かつ安定した反復解法である内点法アルゴリズムが存在しているが、巨大な線形方程式系の計算(行列要素の計算と行列のCholesky分解)が大きなボトルネックとなっている。最近の結果では多数GPU の活用や計算と通信のオーバーラップ技術を応用することによって、主要なボトルネックの1つである線形方程式系のCholesky 分解の高速化と世界最大規模の SDPを高速に解くことに成功した(最大で1.713PFlopsの性能を達成).

Language：English   Publishing type：Research paper (other academic)  

Breadth-first search (BFS) is an important graph analysis kernel. The Graph500 benchmark measures a computer's BFS performance using the traversed edges per second (TEPS) ratio. Our previous nonuniform memory access (NUMA)-optimized BFS reduced memory accesses to remote RAM on a NUMA architecture system; its performance was 11 GTEPS (giga TEPS) on a 4-way Intel Xeon E5-4640 system. Herein, we investigated the computational complexity of the bottom-up, a major bottleneck in NUMA-optimized BFS. We clarify the relationship between vertex out-degree and bottom-up performance. In November 2013, our new implementation achieved a Graph500 benchmark performance of 37.66 GTEPS (fastest for a single node) on an SGI Altix UV1000 (one-rack) and 31.65 GTEPS (fastest for a single server) on a 4-way Intel Xeon E5-4650 system. Furthermore, we achieved the highest Green Graph500 performance of 153.17 MTEPS/W (mega TEPS per watt) on an Xperia-A SO-04E with a Qualcomm Snapdragon S4 Pro APQ8064.

DOI： 10.1007/978-3-319-07518-1-23

Language：English   Publishing type：Research paper (other academic)  

Breadth-first search (BFS) is an important graph analysis kernel. The Graph500 benchmark measures a computer's BFS performance using the traversed edges per second (TEPS) ratio. Our previous nonuniform memory access (NUMA)-optimized BFS reduced memory accesses to remote RAM on a NUMA architecture system; its performance was 11 GTEPS (giga TEPS) on a 4-way Intel Xeon E5-4640 system. Herein, we investigated the computational complexity of the bottom-up, a major bottleneck in NUMA-optimized BFS. We clarify the relationship between vertex out-degree and bottom-up performance. In November 2013, our new implementation achieved a Graph500 benchmark performance of 37.66 GTEPS (fastest for a single node) on an SGI Altix UV1000 (one-rack) and 31.65 GTEPS (fastest for a single server) on a 4-way Intel Xeon E5-4650 system. Furthermore, we achieved the highest Green Graph500 performance of 153.17 MTEPS/W (mega TEPS per watt) on an Xperia-A SO-04E with a Qualcomm Snapdragon S4 Pro APQ8064.

DOI： 10.1007/978-3-319-07518-1_23

Language：English   Publishing type：Research paper (other academic)  

The breadth-first search (BFS) is one of the most important kernels in graph theory. The Graph500 benchmark measures the performance of any supercomputer performing a BFS in terms of traversed edges per second (TEPS). Previous studies have proposed hybrid approaches that combine a well-known top-down algorithm and an efficient bottom-up algorithm for large frontiers. This reduces some unnecessary searching of outgoing edges in the BFS traversal of a small-world graph, such as a Kronecker graph. In this paper, we describe a highly efficient BFS using column-wise partitioning of the adjacency list while carefully considering the non-uniform memory access (NUMA) architecture. We explicitly manage the way in which each working thread accesses a partial adjacency list in local memory during BFS traversal. Our implementation has achieved a processing rate of 11.15 billion edges per second on a 4-way Intel Xeon E5-4640 system for a scale-26 problem of a Kronecker graph with 2(26) vertices and 2(30) edges. Not all of the speedup techniques in this paper are limited to the NUMA architecture system. With our winning Green Graph500 submission of June 2013, we achieved 64.12 GTEPS per kilowatt hour on an ASUS Pad TF700T with an NVIDIA Tegra 3 mobile processor.

DOI： 10.1109/BigData.2013.6691600

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

The second-order reduced density matrix method (the RDM method) has performed well in determining energies and properties of atomic and molecular systems, achieving coupled-cluster singles and doubles with perturbative triples (CCSD (T)) accuracy without using the wave-function. One question that arises is how well does the RDM method perform with the same conditions that result in CCSD (T) accuracy in the strong correlation limit. The simplest and a theoretically important model for strongly correlated electronic systems is the Hubbard model. In this paper, we establish the utility of the RDM method when employing the P,. Q,. G,. T1 and T2' conditions in the two-dimensional Hubbard model case and we conduct a thorough study applying the 4. ×. 4 Hubbard model employing a coefficients. Within the Hubbard Hamiltonian we found that even in the intermediate setting, where U/. t is between 4 and 10, the P, Q, G, T1 and T2' conditions reproduced good ground state energies. © 2012 Elsevier B.V.

DOI： 10.1016/j.comptc.2012.08.018

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

A SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical optimization. SDP provides an effective computation framework for many research fields. Some applications, however, require solving a large-scale SDP whose size exceeds the capacity of a single processor both in terms of computation time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel package) [Yamashita et al. 2003b] was designed to solve such large-scale SDPs. Its parallel performance is outstanding for general SDPs in most cases. However, the parallel implementation is less successful for some sparse SDPs obtained from applications such as Polynomial Optimization Problems (POPs) or Sensor Network Localization (SNL) problems, since this version of SDPARA cannot directly handle sparse Schur Complement Matrices (SCMs). In this article we improve SDPARA by focusing on the sparsity of the SCM and we propose a new parallel implementation using the formula-cost-based distribution along with a replacement of the dense Cholesky factorization. We verify numerically that these features are key to solving SDPs with sparse SCMs more quickly on parallel computing systems. The performance is further enhanced by multithreading and the new SDPARA attains considerable scalability in general. It also finds solutions for extremely large-scale SDPs arising from POPs which cannot be obtained by other solvers.

DOI： 10.1145/2382585.2382591

Language：English   Publishing type：Research paper (other academic)  

Semidefinite programming (SDP) is one of the most important problems among optimization problems at present. It is relevant to a wide range of fields such as combinatorial optimization, structural optimization, control theory, economics, quantum chemistry, sensor network location and data mining. The capability to solve extremely large-scale SDP problems will have a significant effect on the current and future applications of SDP. In 1995, Fujisawa et al. started the SDPA(Semidefinite programming algorithm) Project aimed at solving large-scale SDP problems with high numerical stability and accuracy. SDPA is one of the main codes to solve general SDPs. SDPARA is a parallel version of SDPA on multiple processors with distributed memory, and it replaces two major bottleneck parts (the generation of the Schur complement matrix and its Cholesky factorization) of SDPA by their parallel implementation. In particular, it has been successfully applied to combinatorial optimization and truss topology optimization. The new version of SDPARA (7.5.0-G) on a large-scale supercomputer called TSUBAME 2.0 at the Tokyo Institute of Technology has successfully been used to solve the largest SDP problem (which has over 1.48 million constraints), and created a new world record. Our implementation has also achieved 533 TFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs. © 2012 IEEE.

DOI： 10.1109/SC.2012.67

Language：English  

DOI： 10.1007/978-1-4614-0769-0_24

Language：English   Publishing type：Research paper (other academic)  

Graph500 is a new benchmark for supercomputers based on large-scale graph analysis, which is becoming an important form of analysis in many real-world applications. Graph algorithms run well on supercomputers with shared memory. For the Linpack-based supercomputer rankings, TOP500 reports that heterogeneous and distributed-memory super-computers with large numbers of GPGPUs are becoming dominant. However, the performance characteristics of large-scale graph analysis benchmarks such as Graph500 on distributed-memory supercomputers have so far received little study. This is the first report of a performance evaluation and analysis for Graph500 on a commodity-processor-based distributed-memory supercomputer. We found that the reference implementation "replicated-csr" based on distributed level-synchronized breadth-first search solves a large free graph problem with 231 vertices and 235 edges (approximately 2.15 billon vertices and 34.3 billion edges) in 3.09 seconds with 128 nodes and 3,072 cores. This equates to 11 giga-edges traversed per second. We describe the algorithms and implementations of the reference implementations of Graph500, and analyze the performance characteristics with varying graph sizes and numbers of computer nodes and different implementations. Our results will also contribute to the development of optimized algorithms for the coming exascale machines. © 2011 IEEE.

DOI： 10.1109/IISWC.2011.6114175

Language：Others   Publishing type：Research paper (other academic)  

SemiDefinite Program (SDP) is one of principal problems in mathematical programming. Its application range is very wide and covers some problems arising from control theory; for example, a stability condition for differential inclusions and discrete-time optimal control problems. Solving these applications, however, sometimes requires long computation time, since they generate largescale SDPs. When Primal-Dual Interior-Point Methods (PDIPMs) are employed for solving large-scale SDPs, most of the computation time is occupied by the computation related to the Schur Complement Matrix (SCM). We have developed SDPARA (SemiDefinite Programming Algorithm paRAllel version) to deal with such largescale SDPs. In particular, the latest version of SDPARA can handle sparse SCMs adequately. In this paper, we concisely describe how parallel implementation of SDPARA shortens the computation time of the SCM and then discuss the latest implementation for sparse SCMs. Numerical results show that SDPARA achieves remarkable parallel scalability and enables us to solve large-scale SDPs from control theory. © 2010 IEEE.

DOI： 10.1109/CACSD.2010.5612812

Language：Japanese  

Optimization Software SDPA
The optimization software SDPA which has been developed by our group is a solver for symmetric cone programs. The symmetric cone program is a large scheme which includes linear programs, second-order cone programs and semidefmite programs. It has many applications covering various fields such as combinatorial optimization, systems and control theory, robust optimization and quantum chemistry. Primal-dual interior-point methods, which are polynomial-time algorithms, were proposed to solve symmetric cone programs. SDPA is based on the primal-dual interior-point method. In addition, SDPA utilizes sparsity of data in several ways and parallel computation to solve huge size problems efficiently. Using SDPA, we can obtain the solution of symmetric cone programs easily without knowing the details of the algorithm and its implementation techniques. This paper briefly explain the SDPA and its variants. Then outlines an algorithmic framework of the primal-dual interior-point method.

DOI： 10.11540/bjsiam.18.1_2

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

This paper presents a new solution using the semidefinite programming (SDP) technique to solve the optimal power flow problems (OPF). The proposed method involves reformulating the OPF problems into a SDP model and developing an algorithm of interior point method (IPM) for SDP. That is said, OPF in a nonlinear programming (NP) model, which is a nonconvex problem, has been accurately transformed into a SDP model which is a convex problem. Based on SDP, the OPF problem can be solved by primal-dual interior point algorithms which possess superlinear convergence. The proposed method has been tested with four kinds of objective functions of OPF. Extensive numerical simulations on test systems with sizes ranging from 4 to 300 buses have shown that this method is promising for OPF problems due to its robustness. © 2008.

DOI： 10.1016/j.ijepes.2007.12.003

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

The reduced density matrix (RDM) method, which is a variational calculation based on the second-order reduced density matrix, is applied to the ground state energies and the dipole moments for 57 different states of atoms, molecules, and to the ground state energies and the elements of 2-RDM for the Hubbard model. We explore the well-known N-representability conditions (P, Q, and G) together with the more recent and much stronger T1 and T2(') conditions. T2(') condition was recently rederived and it implies T2 condition. Using these N-representability conditions, we can usually calculate correlation energies in percentage ranging from 100% to 101%, whose accuracy is similar to CCSD(T) and even better for high spin states or anion systems where CCSD(T) fails. Highly accurate calculations are carried out by handling equality constraints and/or developing multiple precision arithmetic in the semidefinite programming (SDP) solver. Results show that handling equality constraints correctly improves the accuracy from 0.1 to 0.6 mhartree. Additionally, improvements by replacing T2 condition with T2(') condition are typically of 0.1-0.5 mhartree. The newly developed multiple precision arithmetic version of SDP solver calculates extraordinary accurate energies for the one dimensional Hubbard model and Be atom. It gives at least 16 significant digits for energies, where double precision calculations gives only two to eight digits. It also provides physically meaningful results for the Hubbard model in the high correlation limit.

DOI： 10.1063/1.2911696

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

The Semidefinite Program (SDP) has recently attracted much attention of researchers in various fields for the following reasons: (i) It has been intensively studied in both theoretical and numerical aspects. Especially the primal-dual interior-point method is known as a powerful tool for solving large-scale SDPs with accuracy. (ii) Many practical problems in various fields such as combinatorial optimization, control and systems theory, robust optimization and quantum chemistry can be modeled or approximated by using SDPs. (iii) Several software packages for solving SDPs and related problems (ex. the Second-Order Cone Program : SOCP) are available on the Internet. In 1995, we started the SDPA Project aimed for solving large-scale SDPs with numerical stability and accuracy. The SDPA (SemiDefinite Programming Algorithm) is a C++ implementation of a Mehrotra-type primal-dual predictor-corrector interior-point method for solving the standard form SDP and its dual. We have also developed some variants of the SDPA to handle SDPs with various features. The SDPARA is a parallel version of the SDPA on multiple processors and distributed memory, which replaces two major bottleneck components of the SDPA by their parallel implementation using MPI and ScaLAPACK. The SDPARA on parallel computer has attractive features; it can load a large-scale SDP into the distributed memory and solve it in a reasonable time. In this paper, we show through some numerical experiments that the SDPARA attains high performance. The SDPARA-C is an integration of two software SDPARA and SDPA-C which is a primal-dual interior-point method using the positive definite matrix completion technique. The SDPARA-C requires a small amount of memory when we solve sparse SDPs with a large-scale matrix variable and/or a large number of equality constraints. The paper also explains a grid portal system for solving SDPs, which we call the SDPA Online Solver. In this paper, we review the major achievements of the SDPA Project on solving large-scale SDPs. This paper provides an introductory and comprehensive materials for researchers who are interested in practical computational aspects of the SDPs.

DOI： 10.15807/jorsj.50.278

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

Parallel Solver for SemiDefinite Programming

Language：Japanese  

Construction and Operation of the Grid Challenge Testbed
This paper presents a case study to operate the Grid testbed for the Grid Challenge in SACSIS2006. The Grid Challenge is a programming competition on a Grid testbed, which is organized by multiple computing resources installed in universities and laboratories. In the last competition, the Grid testbed with more than 1200 CPUs was operated. The paper shows hardware/software specifications of the Grid testbed, and reports experience of the operation, which includes accounting, job management, and troubleshooting.

Language：English  

DOI： 10.1002/9780470053928.ch9

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

Considering that preprocessing is an important phase in linear programing, it should be more systematically incorporated in semidefinite programing (SDP) solvers. The conversion method proposed by the authors [Fukuda, M., Kojima, M., Murota, K. and Nakata, K., 2000, SIAM Journal on Optimization , 11, 647-674 and Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M. and Murota, K., 2003, Mathematical Programming (Series B) , 95, 303-327] is a preprocessing method for sparse SDPs based on matrix completion. This article proposed a new version of the conversion method, which employs a flop estimation function inside its heuristic procedure. Extensive numerical experiments are included showing the advantage of preprocessing by the conversion method for certain classes of very sparse SDPs.

DOI： 10.1080/10556780512331319523

Language：English   Publishing type：Research paper (other academic)  

The stabilization of nonlinear systems depend strongly on the initial state and the parameters of the systems. The initial state and the parameters with which the system is stabilized can be distinguished by the geometrical structure. It is, however, difficult and sometimes impossible to analyze the structure analytically. Therefore it comes important to show and analyze the structure of the parameters and initial states numerically and visually. In this paper, we present a method to draw and visualize such region and structure in the three dimensional space. In general, the projection of the original high-dimensional space to the lower dimension one is required for using visual analysis. Thus, it is convenient that the viewpoint can be moved, without time loss, in the direction where analyst would like to see. As often as the viewpoint moves, the recomputation as quick as possible is required to realize the quick motion of viewpoint. It is, however, obvious that lots of computation and time are taken to draw the region. Therefore, high performance calculators are needed to realize the real-time drawing. In order to overcome this problem, FPGA and cluster-computing is used in this paper. Then it is demonstrated by illustrative examples that FPGA and cluster-computing shows high performance to draw the region of the parameters and initial state in 3D with which z n+1 = z2n + C can be stabilized, that is Mandelbrot and Julia sets, respectively. ©2005 IEEE.

DOI： 10.1109/IDAACS.2005.283052

Language：English   Publishing type：Research paper (other academic)  

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

Variational calculations of fermion second-order reduced density matrices by semidefinite programming algorithm
null

DOI： 10.1063/1.1360199

Language：Japanese  

TOPOLOGY OPTIMIZATION OF TRUSSES FOR SPECIFIED MULTIPLE LINEAR BUCKLING LOAD FACTORS BY USING SEMIDEFINITE PROGRAMMING
An algorithm based on Semi-Definite Programming (SDP) is proposed for the truss topology optimization problem for specified linear buckling load factor, and optimal topologies of trusses are computed by using the Semi-Definite Programming Algorithm (SDPA). It is well known that optimizing structures for specified buckling load factor is difficult because of non-differentiability of the buckling load factor for the case of multimodal solutions. It is shown, in the examples, that the proposed algorithm is applicable to multimodal cases, and an optimal topology with five-fold buckling load factors is found without any difficulty.

DOI： 10.3130/aijs.66.113_1

Language：English  

Solving Sparse Semidefinite Programs by Matrix Completion(Part 2) (Mathematical Science of Optimization)

Language：English  

Matrix Completion and Semidefinite Programming

Language：Japanese  

半正定値計画問題に対するソフトウェアSDPAの広域並列計算システム

Language：Japanese  

半正定値計画問題に対する内点法ソフトウェア

Language：English  

Semidefinite Programming with the Conjugate Gradient Method

Language：English  

Responsible for pages：総ページ数：v, 136p   Language：Others  

Responsible for pages：総ページ数：xv, 310p   Language：Japanese  

Language：Others  

Language：Others  

Responsible for pages：総ページ数：vi, 174p   Language：Japanese  

Responsible for pages：総ページ数：199p   Language：Others  

Language：Japanese   Book type：General book, introductory book for general audience

Language：Japanese   Book type：General book, introductory book for general audience

Event date： 2016.5

Language：English   Presentation type：Public lecture, seminar, tutorial, course, or other speech  

Venue：ZIB, Berlin   Country：Germany  

Event date： 2016.5

Language：English   Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Event date： 2016.5

Language：English   Presentation type：Oral presentation (general)  

Venue：オースティン   Country：United States  

Event date： 2016.5

Language：Japanese  

Venue：九州大学   Country：Japan  

Event date： 2016.5

Language：Japanese   Presentation type：Oral presentation (invited, special)  

Venue：ヒルトン福岡シーホーク   Country：Japan  

Event date： 2014.5

Language：English  

Venue：Phoenix, AZ   Country：United States  

The semi definite programming (SDP) problem is one of the central problems in mathematical optimization. The primal-dual interior-point method (PDIPM) is one of the most powerful algorithms for solving SDP problems, and many research groups have employed it for developing software packages. However, two well-known major bottlenecks, i.e., the generation of the Schur complement matrix (SCM) and its Cholesky factorization, exist in the algorithmic framework of the PDIPM. We have developed a new version of the semi definite programming algorithm parallel version (SDPARA), which is a parallel implementation on multiple CPUs and GPUs for solving extremely large-scale SDP problems with over a million constraints. SDPARA can automatically extract the unique characteristics from an SDP problem and identify the bottleneck. When the generation of the SCM becomes a bottleneck, SDPARA can attain high scalability using a large quantity of CPU cores and some processor affinity and memory interleaving techniques. SDPARA can also perform parallel Cholesky factorization using thousands of GPUs and techniques for overlapping computation and communication if an SDP problem has over two million constraints and Cholesky factorization constitutes a bottleneck. We demonstrate that SDPARA is a high-performance general solver for SDPs in various application fields through numerical experiments conducted on the TSUBAME 2.5 supercomputer, and we solved the largest SDP problem (which has over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.713 PFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs.

Event date： 2013.10

Language：English  

Venue：Santa Clara, CA   Country：United States  

The breadth-first search (BFS) is one of the most important kernels in graph theory. The Graph500 benchmark measures the performance of any supercomputer performing a BFS in terms of traversed edges per second (TEPS). Previous studies have proposed hybrid approaches that combine a well-known top-down algorithm and an efficient bottom-up algorithm for large frontiers. This reduces some unnecessary searching of outgoing edges in the BFS traversal of a small-world graph, such as a Kronecker graph. In this paper, we describe a highly efficient BFS using column-wise partitioning of the adjacency list while carefully considering the non-uniform memory access (NUMA) architecture. We explicitly manage the way in which each working thread accesses a partial adjacency list in local memory during BFS traversal. Our implementation has achieved a processing rate of 11.15 billion edges per second on a 4-way Intel Xeon E5-4640 system for a scale-26 problem of a Kronecker graph with 2 ²⁶ vertices and 2³⁰ edges. Not all of the speedup techniques in this paper are limited to the NUMA architecture system. With our winning Green Graph500 submission of June 2013, we achieved 64.12 GTEPS per kilowatt hour on an ASUS Pad TF700T with an NVIDIA Tegra 3 mobile processor.

Event date： 2012.11

Language：English  

Venue：Salt Lake City, UT   Country：United States  

Semidefinite programming (SDP) is one of the most important problems among optimization problems at present. It is relevant to a wide range of fields such as combinatorial optimization, structural optimization, control theory, economics, quantum chemistry, sensor network location and data mining. The capability to solve extremely large-scale SDP problems will have a significant effect on the current and future applications of SDP. In 1995, Fujisawa et al. started the SDPA(Semidefinite programming algorithm) Project aimed at solving large-scale SDP problems with high numerical stability and accuracy. SDPA is one of the main codes to solve general SDPs. SDPARA is a parallel version of SDPA on multiple processors with distributed memory, and it replaces two major bottleneck parts (the generation of the Schur complement matrix and its Cholesky factorization) of SDPA by their parallel implementation. In particular, it has been successfully applied to combinatorial optimization and truss topology optimization. The new version of SDPARA (7.5.0-G) on a large-scale supercomputer called TSUBAME 2.0 at the Tokyo Institute of Technology has successfully been used to solve the largest SDP problem (which has over 1.48 million constraints), and created a new world record. Our implementation has also achieved 533 TFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs.

Event date： 2011.11

Language：English  

Venue：Austin, TX   Country：United States  

Graph500 is a new benchmark for supercomputers based on large-scale graph analysis, which is becoming an important form of analysis in many real-world applications. Graph algorithms run well on supercomputers with shared memory. For the Linpack-based supercomputer rankings, TOP500 reports that heterogeneous and distributed-memory super-computers with large numbers of GPGPUs are becoming dominant. However, the performance characteristics of large-scale graph analysis benchmarks such as Graph500 on distributed-memory supercomputers have so far received little study. This is the first report of a performance evaluation and analysis for Graph500 on a commodity-processor-based distributed-memory supercomputer. We found that the reference implementation "replicated-csr" based on distributed level-synchronized breadth-first search solves a large free graph problem with 2³¹ vertices and 2³⁵ edges (approximately 2.15 billon vertices and 34.3 billion edges) in 3.09 seconds with 128 nodes and 3,072 cores. This equates to 11 giga-edges traversed per second. We describe the algorithms and implementations of the reference implementations of Graph500, and analyze the performance characteristics with varying graph sizes and numbers of computer nodes and different implementations. Our results will also contribute to the development of optimized algorithms for the coming exascale machines.

Event date： 2010.9

Language：English  

Venue：Yokohama   Country：Japan  

SemiDefinite Program (SDP) is one of principal problems in mathematical programming. Its application range is very wide and covers some problems arising from control theory; for example, a stability condition for differential inclusions and discrete-time optimal control problems. Solving these applications, however, sometimes requires long computation time, since they generate largescale SDPs. When Primal-Dual Interior-Point Methods (PDIPMs) are employed for solving large-scale SDPs, most of the computation time is occupied by the computation related to the Schur Complement Matrix (SCM). We have developed SDPARA (SemiDefinite Programming Algorithm paRAllel version) to deal with such largescale SDPs. In particular, the latest version of SDPARA can handle sparse SCMs adequately. In this paper, we concisely describe how parallel implementation of SDPARA shortens the computation time of the SCM and then discuss the latest implementation for sparse SCMs. Numerical results show that SDPARA achieves remarkable parallel scalability and enables us to solve large-scale SDPs from control theory.

Event date： 2005.9

Language：English  

Venue：Sofia   Country：Bulgaria  

The stabilization of nonlinear systems depend strongly on the initial state and the parameters of the systems. The initial state and the parameters with which the system is stabilized can be distinguished by the geometrical structure. It is, however, difficult and sometimes impossible to analyze the structure analytically. Therefore it comes important to show and analyze the structure of the parameters and initial states numerically and visually. In this paper, we present a method to draw and visualize such region and structure in the three dimensional space. In general, the projection of the original high-dimensional space to the lower dimension one is required for using visual analysis. Thus, it is convenient that the viewpoint can be moved, without time loss, in the direction where analyst would like to see. As often as the viewpoint moves, the recomputation as quick as possible is required to realize the quick motion of viewpoint. It is, however, obvious that lots of computation and time are taken to draw the region. Therefore, high performance calculators are needed to realize the real-time drawing. In order to overcome this problem, FPGA and cluster-computing is used in this paper. Then it is demonstrated by illustrative examples that FPGA and cluster-computing shows high performance to draw the region of the parameters and initial state in 3D with which z _n+1 = z²_n + C can be stabilized, that is Mandelbrot and Julia sets, respectively.

Event date： 2004.1

Language：English  

Venue：Tokyo   Country：Japan  

The aim of this short article is to show that grid and cluster computing provides tremendous power to optimization methods. The methods that the article picks up are a successive convex relaxation method for quadratic optimization problems, a polyhedral homotopy method for polynomial systems of equations and a primal-dual interior-point method for semidefinite programming problems. Their parallel implementations on grids and clusters together with numerical results are reported.

Event date： 1999.12

Language：English  

Venue：Tokyo   Country：Japan  

We consider the problem of finding two-dimensional association rules for categorical attributes. Suppose we have two conditional attributes A and B both of whose domains are categorical, and one binary target attribute whose domain is {“positive”, “negative”}. We want to split the Cartesian product of domains of A and B into two subsets so that a certain objective function is optimized, i.e., we want to find a good segmentation of the domains of A and B. We consider in this paper the objective function that maximizes the confidence under the constraint of the upper bound of the support size. We first prove that the problem is NP-hard, and then propose an approximation algorithm based on semidefinite programming. In order to evaluate the effectiveness and efficiency of the proposed algorithm, we carry out computational ex- periments for problem instances generated by real sales data consisting of attributes whose domain size is a few hundreds at maximum. Approxi- mation ratios of the solutions obtained measured by comparing solutions for semidefinite programming relaxation range from 76% to 95%. It is observed that the performance of generated association rules are signifi- cantly superior to that of one-dimensional rules.

Language：Japanese  

Country：Japan  

Other Link： http://sdpa.imi.kyushu-u.ac.jp/~fujisawa/research.html

Language：English   Presentation type：Oral presentation (general)  

Venue：Dublin   Country：Ireland  

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：東京ミッドタウンホール&カンファレンス   Country：Japan  

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：北海道科学大学   Country：Japan  

Language：English   Presentation type：Oral presentation (general)  

Venue：Kyushu　University   Country：Japan  

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：ホーテルオークラ神戸   Country：Japan  

Language：English   Presentation type：Symposium, workshop panel (public)  

Venue：New Orleans   Country：United States  

Language：Japanese  

Country：Japan  

Language：Japanese   Presentation type：Symposium, workshop panel (public)  

Venue：九州大学情報基盤研究開発センター   Country：Japan  

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：九州大 学   Country：Japan  

Language：Japanese  

Language：Japanese  

Massive MPI Parallelization for Solving Shortest Vector Problem Based on Ubiquity Generator Framework

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Performance enhancement of multi-human tracking based on K-Shortest Paths by data reduction
<p>Object tracking is a challenging problem and it has been improving dramatically in recent years. In this paper, we perform parallelized multi-object tracking system. Object tracking problem has 2 difficulties; one is to detect objects collect, and the other is to track collect using the collect object detection. Jerome et al. performed a multi-object tracking system using K-Shortest Paths to avoid these problems efficiently. However, it is difficult to calculate in parallel because of the iterations calculation of shortest paths on the graph while changing the weight of graph. In our method, we divided time intervals to apply KSP method from Probability Occupancy Map(POM), which is also obtained via using KSP method. Performance evaluation shows our algorithm is 5.4 times faster than the original KSP with 87&#37; accuracy.</p>

DOI： 10.11517/pjsai.JSAI2018.0_2D103

Language：Japanese  

Hybrid Vehicle Control and Optimization with a New Mathematical Method

DOI： 10.11511/jacc.61.0_1792

Language：Japanese  

大規模グラフ解析と都市OSの開発~ヒト・モノのモビリティに関する新しい数理モデルとその応用~

Language：Others  

Language：Japanese  

ヒト・モノのモビリティの数理モデルと産業応用

Language：Japanese  

ポストペタスケールシステムにおける超大規模グラフ最適化基盤

Language：Japanese  

避難計画モデルに対する辞書式最速流の幾何学的分解と解析

Language：Japanese  

辞書式最速流と深層学習を用いた避難完了時間の予測

Language：Others  

© 2016 IEEE. Graph analysis applications have been widely used in real services such as road-traffic analysis and social network services. Breadth-first search (BFS) is one of the most representative algorithms for such applications; therefore, many researchers have tuned it to maximize performance. On the other hand, owing to the strict power constraints of modern HPC systems, it is necessary to improve power efficiency (i.e., performance per watt) when executing BFS. In this work, we focus on the power efficiency of DRAM and investigate the memory access pattern of a state-of-the-art BFS implementation using a cycle-accurate processor simulator. The results reveal that the conventional address mapping schemes of modern memory controllers do not efficiently exploit row buffers in DRAM. Thus, we propose a new scheme called per-row channel interleaving and improve the DRAM power efficiency by 30.3&#37; compared to a conventional scheme for a certain simulator setting. Moreover, we demonstrate that this proposed scheme is effective for various configurations of memory controllers.

DOI： 10.1109/HPGDMP.2016.010

Language：Japanese  

コードレベル性能最適化が電力効率に与える影響の分析

Language：Japanese  

CPUとDRAMへの電力バジェット配分を考慮したGraph500の性能評価

Language：Japanese  

EXPERIMENTAL ANALYSES OF THE EVACUATION PLANNING MODEL USING LEXICOGRAPHICALLY QUICKEST FLOW
<p>In the case of disasters such as tsunamis, people should be quickly evacuated from the area affected by the disasters. In this article, we consider a dynamic network flow model of the evacuation planning for the people in the affected area. In the model, we represent the evacuation of the people as the dynamic flow, and the effective evacuation plan as the lexicographically quickest flow. More specifically, we show the model in which the capacity constraint of refuges is taken into account. We conduct computational experiments using the geospatial information and census data of local cities in Japan.</p>

DOI： 10.15807/torsj.59.86

Language：Others  

DOI： 10.1007/978-3-319-42432-3

Language：Japanese  

Large-scale Graph Analysis and Development of Urban OS : New Mathematical Models for Mobility Analysis

Language：Japanese  

Fast and power efficient computation for sparse modeling

Language：Japanese  

Fast and Power Efficient Computation for Sparse Modeling

Language：Japanese  

Graph Analysis and Mathematical Optimization Techniques for Realizing Urban OS

Language：Japanese  

Language：English  

© 2014 IEEE. We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 231 vertices and 235 edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 &#37; performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

DOI： 10.1109/BigData.2014.7004270

Language：English  

In this article we propose a simple heuristic algorithm for approaching the maximally predictable portfolio, which is constructed so that return model of the resulting portfolio would attain the largest goodness-of-fit. It is obtained by solving a fractional program in which a ratio of two convex quadratic functions is maximized, and the number of variables associated with its nonconcavity has been a bottleneck in spite of continuing endeavour for its global optimization. The proposed algorithm can be implemented by simply solving a series of convex quadratic programs, and computational results show that it yields within a few seconds a (near) Karush-Kuhn-Tucker solution to each of the instances which were solved via a global optimization method in [H. Konno, Y. Takaya and R. Yamamoto, A maximal predictability portfolio using dynamic factor selection strategy, Int. J. Theor. Appl. Fin. 13 (2010) pp. 355-366]. In order to confirm the solution accuracy, we also pose a semidefinite programming relaxation approach, which succeeds in ensuring a near global optimality of the proposed approach. Our findings through computational experiments encourage us not to employ the global optimization approach, but to employ the local search algorithm for solving the fractional program of much larger size.

DOI： 10.1080/02331934.2012.741237

Language：Japanese  

近年の計算機技術の発展や,数理科学分野におけるアルゴリズムの進歩により,以前では考えられない規模の問題を扱うことができるようになってきた.その一方で,実装したソフトウェアが期待される性能を示さないといった場面も少なくない.本稿ではなぜそのような状況になってしまうのか,現在主流となるNUMAアーキテクチャを有したプロセッサの特性を示し,高速に動作することが求められるアルゴリズム実装の際にどのような点を考慮しながら進めれば良いか,それらの改善方法について解説を行う.

Language：Japanese  

Language：Japanese  

<p>スーパーコンピュータを用いた超大規模なグラフ最適化技術，およびその社会応用の例として，緊急避難シミュレーションを紹介する．</p>

DOI： 10.11517/pjsai.JSAI2014.0_1C5OS13b1

Language：Japanese  

Large-scale graph analysis and its applications using techniques of the next generation super computer

Language：English  

1-F-5 Peta-scale General Solver for Semidefinite Programming : Extremely Large-scale Parallel Cholesky Solver

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

本発表では,NUMA アーキテクチャを有する計算機上で高い性能を示す幅優先探索について説明する.提案手法は汎用的なグラフ分割手法を用いて,プロセッサソケットと対となるローカルメモリを考慮し,局所性を高めることに成功している.本研究で開発した実装は,HPC 分野において注目されている幅優先探索の性能を用いたベンチマーク Graph500 の 1 ノード最高性能を,幅優先探索の省電力性能を用いたベンチマーク Green Graph500 では世界 1 位をそれぞれ獲得している.

Language：Japanese  

近年、SNS 解析、道路ネットワークの経路探索、スマートグリッド、創薬、遺伝子解析等の様々な分野で大規模なグラフに対する高速処理が求められているが、従来手法では、妥当な性能を得るためには全てのデータを DRAM 上にロードして実行する必要があり、その結果、DRAM の容量を増設することによる消費電力、価格の面でのコストの増加が問題になっている。そこで、我々は、BFS に対して NVM(不揮発性メモリ) を補助的に利用することで、DRAM の容量を超えるサイズのグラフを性能低下を抑えながら高速に処理する手法を提案し、開発を進めている。現時点で、省電力なビッグデータ処理のランキングである GreenGraph500 (2013 年 11 月) のビッグデータカテゴリのリストで 4 位 (1 ノードでは世界一) を達成した。

Language：Japanese  

近年,大規模かつ複雑な最適化問題を高速に解く需要はさまざまな産業界や学術分野において急速に高まりつつある.これからの研究においては最先端理論(Theory)+超大規模実データ(Practice)+最新計算技術(Computation)の三つを有機的に組み合わせることによって,実用に耐えうる解決策の提示と大規模最適化問題を扱う際の先例となることが求められている.本稿では最適化と計算に関する最新の傾向に触れるとともに,最適化の計算の今後についても考えていきたい.

Language：English  

Language：Japanese  

Fast implementation of shared-memory parallel algorithm using ULIBC (Ubiquity Library for Intelligently Binding Cores)

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

近年さまざまな分野で大規模なグラフに対する高速な処理が求められているが,その処理の特性上,妥当な性能を得るためには全てのデータを DRAM 上にロードして実行する必要があり,その結果,DRAM の容量を増設することによる消費電力,価格面でのコストの増加が問題となっている.そこで,Hybrid-BFS アルゴリズムに対して不揮発性メモリを補助的に利用した場合の I/O の最適化,性能低下要因の解析を行うことで性能低下を抑えながら大規模グラフ処理が実行可能かの評価を行った.その結果,一部データを不揮発性メモリに退避することで DRAM 用量が半分の環境において性能低下を 47.1&#37; まで抑えることができた.また,参照され難いエッジデータをさらに退避することで性能の低下を抑えながらより DRAM 使用量が削減可能なことの確認,さらに,性能低下要因の特定とその改善案を示し,性能低下を抑えながら大規模グラフ処理の実現可能性が示唆された.

Language：Japanese  

Solving Extremely Large-scale Semidefinite Optimization Problems via Parallel Computation of Interior-point Method

Language：Japanese  

Language：Japanese  

近年大規模グラフはさまざまな分野で出現しており，DRAM の容量を増設することによる消費電力増加の問題やそもそもシングルノード上の DRAM 容量を超えるグラフも出現している．本研究ではGraph 500 ベンチマークに対して不揮発性メモリを補助的に利用することで性能低下を最小限に押さえながらシングルノード上でできる限り大容量のグラフを扱えるようにすることを目指している．そこでまず本論文ではDRAM に乗りきらない問題サイズを実行するための手法を提案し，DRAM と不揮発性メモリの容量の比率が実行性能にどのような影響を与えるかについての予備評価を行った．

Language：Others  

Parallel Computing for Large-scale Semidefinite Programs

Language：English  

The second-order reduced density matrix method (the RDM method) has performed well in determining energies and properties of atomic and molecular systems, achieving coupled-cluster singles and doubles with perturbative triples (CCSD (T)) accuracy without using the wave-function. One question that arises is how well does the RDM method perform with the same conditions that result in CCSD (T) accuracy in the strong correlation limit. The simplest and a theoretically important model for strongly correlated electronic systems is the Hubbard model. In this paper, we establish the utility of the RDM method when employing the P,. Q,. G,. T1 and T2' conditions in the two-dimensional Hubbard model case and we conduct a thorough study applying the 4. ×. 4 Hubbard model employing a coefficients. Within the Hubbard Hamiltonian we found that even in the intermediate setting, where U/. t is between 4 and 10, the P, Q, G, T1 and T2' conditions reproduced good ground state energies.

DOI： 10.1016/j.comptc.2012.08.018

Language：Japanese  

High-Performance General Solver for Extremely Large-Scale Semidefinite Programming Problems

Language：English  

A SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical optimization. SDP provides an effective computation framework for many research fields. Some applications, however, require solving a large-scale SDP whose size exceeds the capacity of a single processor both in terms of computation time and available memory. SDPARA (SemiDefinite Programming Algorithm parallel package) [Yamashita et al. 2003b] was designed to solve such large-scale SDPs. Its parallel performance is outstanding for general SDPs in most cases. However, the parallel implementation is less successful for some sparse SDPs obtained from applications such as Polynomial Optimization Problems (POPs) or Sensor Network Localization (SNL) problems, since this version of SDPARA cannot directly handle sparse Schur Complement Matrices (SCMs). In this article we improve SDPARA by focusing on the sparsity of the SCM and we propose a new parallel implementation using the formula-cost-based distribution along with a replacement of the dense Cholesky factorization. We verify numerically that these features are key to solving SDPs with sparse SCMs more quickly on parallel computing systems. The performance is further enhanced by multithreading and the new SDPARA attains considerable scalability in general. It also finds solutions for extremely large-scale SDPs arising from POPs which cannot be obtained by other solvers.

DOI： 10.1145/2382585.2382591

Language：Others  

DOI： 10.1007/978-1-4614-0769-0_24

Language：Others  

The second-order reduced density matrix method (the RDM method) has performed
well in determining energies and properties of atomic and molecular systems,
achieving coupled-cluster singles and doubles with perturbative triples (CC
SD(T)) accuracy without using the wave-function. One question that arises is
how well does the RDM method perform with the same conditions that result in
CCSD(T) accuracy in the strong correlation limit. The simplest and a
theoretically important model for strongly correlated electronic systems is the
Hubbard model. In this paper, we establish the utility of the RDM method when
employing the &#36;P&#36;, &#36;Q&#36;, &#36;G&#36;, &#36;T1&#36; and &#36;T2^prime&#36; conditions in the
two-dimension al Hubbard model case and we conduct a thorough study applying
the &#36;4 imes 4&#36; Hubbard model employing a coefficients. Within the Hubbard
Hamilt onian we found that even in the intermediate setting, where &#36;U/t&#36; is
between 4 and 10, the &#36;P&#36;, &#36;Q&#36;, &#36;G&#36;, &#36;T1&#36; and &#36;T2^prime&#36; conditions re
produced good ground state energies.

DOI： 10.1016/j.comptc.2012.08.018

Language：Japanese  

Language：Japanese  

Evaluating Peformance of SDP Solver on PGAS Language X10

Language：Others  

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

Language：Others  

Language：English  

Language：English  

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.

DOI： 10.15807/jorsj.54.259

Language：Japanese  

NETAL: High-Performance Implementation of NETwork Analysis Library Considering Computer Memory Hierarchy
The use of network analysis has increased in various fields. The large amounts of computation required for dealing with large-scale networks is a major hurdle. We propose an efficient multithreaded computation which considers computer memory hierarchy on general computing environments to solve the shortest paths and the centrality metrics. Our implementation, called NETAL (NETwork Analysis Library), configures the processor core and local memory allocation (affinity), to avoid computational resource request conflicts by considering the difference in distances between processor cores and the RAM within the NUMA architecture of the AMD Opteron 6174. We demonstrated through tests on real-world networks that NETAL is faster than previous implementations. NETAL succeeded in solving the exact shortest path distance table for the USA-road-d.USA.gr (n =24M, m =58M) 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 reference solver. Furthermore, while it took GraphCT 21 days to compute the exact betweenness of USA-road-d.LKS.gr, our implementation computed multiple centrality metrics (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.

Language：Japanese  

最適化問題に対するクラウド・コンピューティングの適用には様々な方法が提案されている.例えば大規模最適化問題に対して数値実験等を行うために,必要なときに,必要な量だけ計算機資源をインターネット上から調進してくるIaaSと呼ばれる技術の利用等がある.本解説ではこの利用方法に関連するクラウド技術による計算資源の動的な確保について触れてから,最適化問題として大規模なネットワークデータにおけるグラフ探索と応用,およびクラウド・コンピューティングの技術を用いた高速化などに関する話題について説明していく.

Language：Japanese  

FAST IMPLEMENTATION OF DIJKSTRA'S ALGORITHM FOR THE LARGE-SCALE SHORTEST PATH PROBLEM
The shortest path problem can be widely applied not only to route search in large-scale network but to other optimization problems where the shortest path problems are used as subproblems. Although there exist stable and efficient algorithms for the shortest path problem, we need fast implementations when solving large-scale shortest path problems. In this paper, we discuss how to make fast and general implementations of Dijkstra's algorithm, where the memory hierarchy is carefully considered to specify the bottleneck of the algorithm and to improve the performance. Our implementations with the binary heap are superior to other existing implementations when taking three factors (performance, robustness, and required computational memory) into consideration. We show that our implementations can get optimal routes very quickly and require smaller computational memory compared with other implementations through systematic numerical experiments. We also explain the Web service for large-scale shortest path problems, which employs our implementations.

DOI： 10.15807/torsj.54.58

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Others  

The reduced-density-matrix method is an promising candidate for the next
generation electronic structure calculation method; it is equivalent to solve
the Schr"odinger equation for the ground state. The number of variables is the
same as a four electron system and constant regardless of the electrons in the
system. Thus many researchers have been dreaming of a much simpler method for
quantum mechanics. In this chapter, we give a overview of the reduced-density
matrix method; details of the theories, methods, history, and some new
computational results. Typically, the results are comparable to the CCSD(T)
which is a sophisticated traditional approach in quantum chemistry.

Language：Japanese  

Language：Japanese  

"Bare Metal" Cloud : A cloud service delivering real machines

Language：Japanese  

Language：Japanese  

最適化ソフトウェアに関連性の高い情報技術には,マルチコア・プロセッサ,GPUコンピューティング,スーパーコンピュータ,クラウド・コンピューティングなどがある.これらの新技術が個別あるいは複合して最適化ソフトウェアとどのように絡んでくるのか,あるいはどのように活用すれば性能向上などの成果を上げることができるのかについては,最新の研究成果を含めてあまり知られていない.そこで本解説では,著者らのグループによる半正定値計画問題(SDP)に対するソフトウェア開発を題材にして,最先端の最適化アルゴリズムと最新の情報技術の有機的な融合方法等について触れていく.

Language：Japanese  

Usage and Performance of SDP solvers

DOI： 10.11509/sci.SCI10.0.320.0

Language：Japanese  

Language：Japanese  

New technologies in the SDPA project

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：English  

SDPA Project and New Features of SDPA 7.1.0 (High Performance Algorithms for Computational Science and Their Applications)

Language：Japanese  

Language：Japanese  

Language：Others  

A new method using semi-definite programming (SDP) to solve optimal power flow (OPF) problems was presented. Named as SDP-OPF, the proposed method involves reformulating the OPF problem into a SDP model, which is a convex problem, and developing an interior point method (IPM) for SDP. Furthermore, the SDP sparsity technique can greatly improve the efficiency of storage and computing. A simple 4-bus power system was employed to explain the implementation process, which includes converting the OPF problem to the SDP model and mapping the results of SDP's to the OPF solutions. Extensive numerical simulations show that the results by SDP-OPF are the same as by NLP-OPF. SDP-OPF has the super-linear convergence, and it can guarantee the global optimal solutions within the polynomial times. Therefore, the study for SDP-OPF offers a good prospect.

Language：English  

This paper presents a new solution using the semidefinite programming (SDP) technique to solve the optimal power flow problems (OPF). The proposed method involves reformulating the OPF problems into a SDP model and developing an algorithm of interior point method (IPM) for SDP. That is said, OPF in a nonlinear programming (NP) model, which is a nonconvex problem, has been accurately transformed into a SDP model which is a convex problem. Based on SDP, the OPF problem can be solved by primal-dual interior point algorithms which possess superlinear convergence. The proposed method has been tested with four kinds of objective functions of OPF. Extensive numerical simulations on test systems with sizes ranging from 4 to 300 buses have shown that this method is promising for OPF problems due to its robustness.

DOI： 10.1016/j.ijepes.2007.12.003

Language：English  

A new method using semi-definite programming (SDP) to solve optimal power flow (OPF) problems was presented. Named as SDP-OPF, the proposed method involves reformulating the OPF problem into a SDP model, which is a convex problem, and developing an interior point method (IPM) for SDP. Furthermore, the SDP sparsity technique can greatly improve the efficiency of storage and computing. A simple 4-bus power system was employed to explain the implementation process, which includes converting the OPF problem to the SDP model and mapping the results of SDP's to the OPF solutions. Extensive numerical simulations show that the results by SDP-OPF are the same as by NLP-OPF. SDP-OPF has the super-linear convergence, and it can guarantee the global optimal solutions within the polynomial times. Therefore, the study for SDP-OPF offers a good prospect.

Language：English  

The reduced density matrix (RDM) method, which is a variational calculation based on the second-order reduced density matrix, is applied to the ground state energies and the dipole moments for 57 different states of atoms, molecules, and to the ground state energies and the elements of 2-RDM for the Hubbard model. We explore the well-known N -representability conditions (P, Q, and G) together with the more recent and much stronger T1 and T 2′ conditions. T 2′ condition was recently rederived and it implies T2 condition. Using these N -representability conditions, we can usually calculate correlation energies in percentage ranging from 100% to 101%, whose accuracy is similar to CCSD(T) and even better for high spin states or anion systems where CCSD(T) fails. Highly accurate calculations are carried out by handling equality constraints and/or developing multiple precision arithmetic in the semidefinite programming (SDP) solver. Results show that handling equality constraints correctly improves the accuracy from 0.1 to 0.6 mhartree. Additionally, improvements by replacing T2 condition with T 2′ condition are typically of 0.1-0.5 mhartree. The newly developed multiple precision arithmetic version of SDP solver calculates extraordinary accurate energies for the one dimensional Hubbard model and Be atom. It gives at least 16 significant digits for energies, where double precision calculations gives only two to eight digits. It also provides physically meaningful results for the Hubbard model in the high correlation limit.

DOI： 10.1063/1.2911696

Language：Japanese  

Language：English  

The Semidefinite Program (SDP) has recently attracted much attention of researchers in various fields for the following reasons: (i) It has been intensively studied in both theoretical and numerical aspects. Especially the primal-dual interior-point method is known as a powerful tool for solving large-scale SDPs with accuracy. (ii) Many practical problems in various fields such as combinatorial optimization, control and systems theory, robust optimization and quantum chemistry can be modeled or approximated by using SDPs. (iii) Several software packages for solving SDPs and related problems (ex. the Second-Order Cone Program : SOCP) are available on the Internet. In 1995, we started the SDPA Project aimed for solving large-scale SDPs with numerical stability and accuracy. The SDPA (SemiDefinite Programming Algorithm) is a C++ implementation of a Mehrotra-type primal-dual predictor-corrector interior-point method for solving the standard form SDP and its dual. We have also developed some variants of the SDPA to handle SDPs with various features. The SDPARA is a parallel version of the SDPA on multiple processors and distributed memory, which replaces two major bottleneck components of the SDPA by their parallel implementation using MPI and ScaLAPACK. The SDPARA on parallel computer has attractive features; it can load a large-scale SDP into the distributed memory and solve it in a reasonable time. In this paper, we show through some numerical experiments that the SDPARA attains high performance. The SDPARA-C is an integration of two software SDPARA and SDPA-C which is a primal-dual interior-point method using the positive definite matrix completion technique. The SDPARA-C requires a small amount of memory when we solve sparse SDPs with a large-scale matrix variable and/or a large number of equality constraints. The paper also explains a grid portal system for solving SDPs, which we call the SDPA Online Solver. In this paper, we review the major achievements of the SDPA Project on solving large-scale SDPs. This paper provides an introductory and comprehensive materials for researchers who are interested in practical computational aspects of the SDPs.

DOI： 10.15807/jorsj.50.278

Language：Japanese  

数年前からクラスタやグリッドなどの並列計算技術が広く普及し,多くの分野に適用されて成功を収めている.最近ではマルチコアを搭載したプロセッサの登場によって,さらに簡単,安価に並列計算の適用が行えるようになった.本稿では最適化問題をめぐる並列計算技術の現状に触れた後,最適化問題として半正定値計画問題を取り上げ,並列計算の適用に関する実験結果と考察等を報告する

Language：Japanese  

大規模最適化問題を解くための試みは様々な分野で行われているが,実用的なレベルで問題を解くためにはアルゴリズムの改良だけでなく,最新の情報技術を駆使して大規模な計算基盤上で並列計算を行うことも必要である.本解説では大規模最適化問題として半正定値計画問題(SDP)とSDPを解くためのソフトウェアSDPAを取り上げ,SDPの定義,例題や利用法などを簡単に説明した後で,SDPAで採用したアルゴリズム,超大規模なSDPに対する数値実験結果,クラスタ&グリッド技術を用いたSDPA Online Solverなどについて解説を行う.

Language：English  

The polyhedral homotopy continuation method is known to be a successful method for finding all isolated solutions of a system of polynomial equations. PHoM, an implementation of the method in C++, finds all isolated solutions of a polynomial system by constructing a family of modified polyhedral homotopy functions, tracing the solution curves of the homotopy equations, and verifying the obtained solutions. A software package PHoMpara parallelizes PHoM to solve a polynomial system of large size. Many characteristics of the polyhedral homotopy continuation method make parallel implementation efficient and provide excellent scalability. Numerical results include some large polynomial systems that had not been solved.

DOI： 10.1007/s00607-006-0166-2

Language：English  

The polyhedral homotopy continuation method is known to be a successful method for finding all isolated solutions of a system of polynomial equations. PHoM, an implementation of the method in C++, finds all isolated solutions of a polynomial system by constructing a family of modified polyhedral homotopy functions, tracing the solution curves of the homotopy equations, and verifying the obtained solutions. A software package PHoMpara parallelizes PHoM to solve a polynomial system of large size. Many characteristics of the polyhedral homotopy continuation method make parallel implementation efficient and provide excellent scalability. Numerical results include some large polynomial systems that had not been solved.

DOI： 10.1007/s00607-006-0166-2

Language：Japanese  

COST PLANNING SYSTEM FOR PUBLIC BUILDING CONSTRUCTION PROJECTS(Building Economics and Housing Problems)
The purpose of the this research is to develop the cost planning system to be used step by step during the production process on construction projects of public offices. The purposes of the research are as follows. 1)System development for cost planning to achieve business decisions. 2)Improvement for traditional cost planning system by public clients. 3)System development for change order and Value Engineering clarified predictable construction costs. 4)System development to reduce workloads for estimating construction costs.

DOI： 10.3130/aijt.12.437

Language：Others  

DOI： 10.1002/9780470053928.ch9

Language：English  

Considering that preprocessing is an important phase in linear programing, it should be more systematically incorporated in semidefinite programing (SDP) solvers. The conversion method proposed by the authors [Fukuda, M., Kojima, M., Murota, K. and Nakata, K., 2000, SIAM Journal on Optimization , 11, 647-674 and Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M. and Murota, K., 2003, Mathematical Programming (Series B) , 95, 303-327] is a preprocessing method for sparse SDPs based on matrix completion. This article proposed a new version of the conversion method, which employs a flop estimation function inside its heuristic procedure. Extensive numerical experiments are included showing the advantage of preprocessing by the conversion method for certain classes of very sparse SDPs.

DOI： 10.1080/10556780512331319523

Language：Others  

A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of its coefficient matrix. SDPARA can effectively solve SDPs with a large number of equality constraints; however, it does not solve SDPs with a large scale matrix variable with similar effectiveness. SDPA-C is a primal-dual interior-point method using the positive definite matrix completion technique by Fukuda et al., and it performs effectively with SDPs with a large scale matrix variable, but not with a large number of equality constraints. SDPARA-C benefits from the strong performance of each of the two methods. Furthermore, SDPARA-C is designed to attain a high scalability by considering most of the expensive computations involved in the primal-dual interior-point method. Numerical experiments with the three parallel software packages SDPARA-C, SDPARA and PDSDP by Benson show that SDPARA-C efficiently solves SDPs with a large scale matrix variable as well as a large number of equality constraints with a small amount of memory. © 2005 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.parco.2005.07.002

Language：English  

A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of its coefficient matrix. SDPARA can effectively solve SDPs with a large number of equality constraints; however, it does not solve SDPs with a large scale matrix variable with similar effectiveness. SDPA-C is a primal-dual interior-point method using the positive definite matrix completion technique by Fukuda et al., and it performs effectively with SDPs with a large scale matrix variable, but not with a large number of equality constraints. SDPARA-C benefits from the strong performance of each of the two methods. Furthermore, SDPARA-C is designed to attain a high scalability by considering most of the expensive computations involved in the primal-dual interior-point method. Numerical experiments with the three parallel software packages SDPARA-C, SDPARA and PDSDP by Benson show that SDPARA-C efficiently solves SDPs with a large scale matrix variable as well as a large number of equality constraints with a small amount of memory.

DOI： 10.1016/j.parco.2005.07.002

Language：Japanese  

Language：Japanese  

Language：English  

SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(<Special Issue>Network Design, Control and Optimization)
Solving large scale optimization problems requires a huge amount of computational power. The size of optimization problems that can be solved on a few CPUs has been limited due to a lack of computational power. Grid and cluster computing has received much attention as a powerful and inexpensive way of solving large scale optimization problems that an existing single-unit CPU cannot process. The aim of this paper is to show that grid and cluster computing provides tremendous power to optimization methods. The methods that this paper picks up are a successive convex relaxation method for quadratic optimization problems, a polyhedral homotopy method for polynomial systems of equations and a primal-dual interiorpoint method for semidefinite programs. Their parallel implementations on grids and clusters together with numerical results are reported. The paper also mentions a grid portal system for optimization problems briefly.

DOI： 10.15807/jorsj.47.265

Language：English  

The aim of this short article is to show that grid and cluster computing provides tremendous power to optimization methods. The methods that the article picks up are a successive convex relaxation method for quadratic optimization problems, a polyhedral homotopy method for polynomial systems of equations and a primal-dual interior-point method for semidefinite programming problems. Their parallel implementations on grids and clusters together with numerical results are reported.

Language：English  

PHoM is a software package in C++ for finding all isolated solutions of polynomial systems using a polyhedral homotopy continuation method. Among three modules constituting the package, the first module StartSystem constructs a family of polyhedral-linear homotopy functions, based on the polyhedral homotopy theory, from input data for a given system of polynomial equations f(x)=0. The second module CMPSc traces the solution curves of the homotopy equations to compute all isolated solutions of f(x)=0. The third module Verify checks whether all isolated solutions of f(x)=0 have been approximated correctly. We describe numerical methods used in each module and the usage of the package. Numerical results to demonstrate the performance of PHoM include some large polynomial systems that have not been solved previously.

DOI： 10.1007/s00607-003-0032-4

Language：Japanese  

A Challenge to Large Scale Optimization Problem - Applications of Grid & Cluster Computing -

Language：Japanese  

Language：English  

PHoM is a software package in C++ for finding all isolated solutions of polynomial systems using a polyhedral homotopy continuation method. Among three modules constituting the package, the first module StartSystem constructs a family of polyhedral-linear homotopy functions, based on the polyhedral homotopy theory, from input data for a given system of polynomial equations f(x) = 0. The second module CMPSc traces the solution curves of the homotopy equations to compute all isolated solutions of f(x) = 0. The third module Verify checks whether all isolated solutions of f(x) = 0 have been approximated correctly. We describe numerical methods used in each module and the usage of the package. Numerical results to demonstrate the performance of PHoM include some large polynomial systems that have not been solved previously.

DOI： 10.1007/s00607-003-0032-4

Language：English  

Solving large scale optimization problems requires a huge amount of computational power. The size of optimization problems that can be solved on a few CPUs has been limited due to a lack of computational power. Grid and cluster computing has received much attention as a powerful and inexpensive way of solving large scale optimization problems that an existing single-unit CPU cannot process. The aim of this paper is to show that grid and cluster computing provides tremendous power to optimization methods. The methods that this paper picks up are a successive convex relaxation method for quadratic optimization problems, a polyhedral homotopy method for polynomial systems of equations and a primal-dual interior-point method for semidefinite programs. Their parallel implementations on grids and clusters together with numerical results are reported. The paper also mentions a grid portal system for optimization problems briefly.

DOI： 10.15807/jorsj.47.265

Language：Japanese  

CORRELATION ANALYSIS BETWEEN PHOTOS OF INTERNAL SPACE AND SUBJECTIVE IMPRESSION USING TWO-DIMENSIONAL WAVELET TRANSFORM
When one experinces an architectural space, he/she perceives various impressions. The purpose of this paper is to quantitatively clarify the relationship between the impression perceived on a photo of an architectural internal space and the phsical features of its color image. For fifty sample color images of internal space, we have performed a questionaire concerning what impression he/she acquires for each image by asking him/her to choose one of the impression words from a pair of antonyms. Also, we have computed color and texture features of photos. Here we used two-dimensional wavelet transform to obtain texture features while Lab-color space is used to extract color features. We then applied a decision-tree algorithm in order to derive interpretable and meaningful correlation of the impression words and image features. As a result, for images for which a majority of people had the same impression, we have found an interesting, interpretable common feature among the images.

DOI： 10.3130/aije.68.133

Language：Japanese  

The Survey of Softwares for the Semidefinite Programming

Language：Others  

The SDPA (SemidDefinite Programming Algorithm) is known as efficient computer software based on the primal-dual interior-point method for solving SDPs (SemiDefinite Programs). In many applications, however, some SDPs become larger and larger, too large for the SDPA to solve on a single processor. In execution of the SDPA applied to large scale SDPs, the computation of the so-called Schur complement matrix and its Cholesky factorization consume most of the computational time. The SDPARA (SemiDefinite Programming Algorithm paRAllel version) is a parallel version of the SDPA on multiple processors and distributed memory, which replaces these two parts by their parallel implementation using MPI and ScaLAPACK. Through numerical results, we show that the SDPARA on a PC cluster consisting of 64 processors attains high scalability for large scale SDPs without losing the stability of the SDPA. © 2003 Elsevier B.V. All rights reserved.

DOI： 10.1016/S0167-8191(03)00087-5

Language：English  

SDP (SemiDefinite Programming) is one of the most attractive optimization models. It has many applications from various fields such as control theory, combinatorial and robust optimization, and quantum chemistry. The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs based on primal-dual interior-point methods with the HRVW/KSH/M search direction. It is written in C++ with the help of LAPACK for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance for large scale problems through numerical experiments and comparisons with some other major software packages for general SDPs.

DOI： 10.1080/1055678031000118482

Language：English  

SDP (SemiDefinite Programming) is one of the most attractive optimization models. It has many applications from various fields such as control theory, combinatorial and robust optimization, and quantum chemistry. The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs based on primal-dual interior-point methods with the HRVW/KSH/M search direction. It is written in C++ with the help of LAPACK for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance for large scale problems through numerical experiments and comparisons with some other major software packages for general SDPs.

DOI： 10.1080/1055678031000118482

Language：English  

The SDPA (SemidDefinite Programming Algorithm) is known as efficient computer software based on the primal-dual interior-point method for solving SDPs (SemiDefinite Programs). In many applications, however, some SDPs become larger and larger, too large for the SDPA to solve on a single processor. In execution of the SDPA applied to large scale SDPs, the computation of the so-called Schur complement matrix and its Cholesky factorization consume most of the computational time. The SDPARA (SemiDefinite Programming Algorithm paRAllel version) is a parallel version of the SDPA on multiple processors and distributed memory, which replaces these two parts by their parallel implementation using MPI and ScaLAPACK. Through numerical results, we show that the SDPARA on a PC cluster consisting of 64 processors attains high scalability for large scale SDPs without losing the stability of the SDPA.

DOI： 10.1016/S0167-8191(03)00087-5

Language：Japanese  

Language：English  

In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix completion itself in a primal-dual interior-point method. The current article presents the details of their implementations. We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient for some problems.

DOI： 10.1007/s10107-002-0351-9

Language：English  

In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix completion itself in a primal-dual interior-point method. The current article presents the details of their implementations. We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient for some problems.

DOI： 10.1007/s10107-002-0351-9

Language：Japanese  

High Performance Grid Computing for Optimization Problem (Mathematics and Algorithms of Optimization)

Language：Japanese  

11022 Correlation Analysis between Photos of Internal Space and Perceptual Image using Wavelet Analysis

Language：Others  

Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems

Language：Japanese  

CONSTRUCTION PLANNING OF REPETITIVE WORK WITH THEORY OF CONSTRAINTS
The daily number of work labor is radical changeable in a jobsite when the contractors build a construction project. To improve this situation, various construction-planning methods were studied. But in recent years, because the building become high-rise and large-scale, it is very difficult to plan schedule with effective building production using past planning method, and construction planning included repetitive schedule is frequently planned. There are many past studies about construction planning of repetitive work, but until now, schedule planning is still depended on experience of the manager of construction site. Then, in this paper, the authors build a model of repetitive work, and search the optimization of this schedule planning with theory of constraints.

DOI： 10.3130/aija.67.281_4

Language：English  

ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
An interesting combinatorial (enumeration) problem arises in the initial phase of the polyhedral homotopy continuation method for computing all solutions of a polynomial equation system in complex variables. It is formulated as a problem of finding all solutions of a specially structured system of linear inequalities with a certain additional combinatorial condition. This paper presents a computational method for the problem fully utilizing the duality theory and the simplex method for linear programs, and report numerical results on a single cpu implementation and a parallel cpu implementation of the method.

DOI： 10.15807/jorsj.45.64

Language：Japanese  

Optimization of Sub-package Problem in Building Construction Project : Proposal of Sub-package Support System
A single construction project is undertaken by a multitude of firms comprised of a prime contractor and many subcontractors. Generally, these organizations are assembled only for the period of the construction project. The success of the project depends largely on whether subcontractor organizations can be properly engaged and managed. The general contractor has the right to define the work scope for each component of the construction project and to assign the subcontractor to carry out each subtask. Therefore, it is very important for the general contractor to develop a good subcontractor team based on the specific characteristics of each project. In this paper, we present a new concept of a sub-package problem by focusing on its management time and cost. Also, we formulate the sub-package problem as a mathematical programming model through which we demonstrate some numerical results.

DOI： 10.11540/jsiamt.12.1_9

Language：Japanese  

1995年に多面体ホモトピー法が提案されて以来,多項式方程式系の全根列挙問題に関する研究は飛躍的に発展してきた.多面体ホモトピー法はそれまでのホモトピー法に比べて計算量が少なく済むという素晴らしい性質を持つ反面,ホモトピー法に必要な"初期方程式系"を形成するために「条件付き線形不等式系に対する全解列挙」という新たな組合せ問題が生じてしまう.現在,多項式方程式系の全根列挙に必要な計算時間の約3分の1が,この組合せ問題を解くことに費されており,この部分の高速化が望まれている.本論文では,条件付き線形不等式系の全解列挙問題に対して,線形計画法の感度分析テクニック,双対理論を使ったアルゴリズムを提案する.また,本アルゴリズムに対して効率の良い並列計算処理が可能であり,並列計算機に実装した結果,今まで解けなかった規模の問題まで扱えるようになった.本アルゴリズムの必要とする計算機メモリーや計算時間などを既存の実験結果と比べることにより,その有効性を検証する.

Language：English  

An interesting combinatorial (enumeration) problem arises in the initial phase of the polyhedral homotopy continuation method for computing all solutions of a polynomial equation system in complex variables. It is formulated as a problem of finding all solutions of a specially structured system of linear inequalities with a certain additional combinatorial condition. This paper presents a computational method for the problem fully utilizing the duality theory and the simplex method for linear programs, and report numerical results on a single cpu implementation and a parallel cpu implementation of the method.

DOI： 10.15807/jorsj.45.64

Language：Japanese  

DEVELOPMENT OF A METHOD FOR DETECTING VANISHING POINTS OF AN ARCHITECTURAL IMAGE AND RECONSTRUCTING A 3D ARCHITECTURAL MODEL
We present a method for detecting vanishing points of an architectural image, which consists of mainly parallel and orthogonal lines, and reconstructing a 3D architectural model. For this, we implement an algorithm for line detection from an architectural image, based on the Hough Transform employing the plane sweep technique and test its efficiency and ability of the line detection from digital images. We then apply it to architectural images in order to see the practical usefulness of the proposed method.

DOI： 10.3130/aija.66.269_1

Language：Japanese  

STUDY ON WORKING DRAWINGS AND SHOP DRAWINGS SCHEDULING
The objectives that this paper has aimed at are as follows: 1) To develop a system which can quantitatively indicate the influence on the project cost by focusing on the finish time of working drawings and shop drawings. 2) To propose the method of optimizing the schedule of making working drawings and shop drawings under consideration of various constrained conditions. Using this system, the owner of the project can get theoretical background for the adjustment of the conflict between the design team and the construction team from the point of the optimization of the project cost in the schedule of making working drawings and shop drawings. As local search is one of the most effective heuristic algorithms for optimization problem, it is applied to the optimization of the schedule of making working drawings and shop drawings.

DOI： 10.3130/aija.66.223_5

Language：Japanese  

Language：English  

The DMVT was developed systematically by using semidefinite programming algorithm (SDPA) as a problem solver. It was shown that the technique is very stable. Although errors were found, these are permissible in both energy and properties.

DOI： 10.1063/1.1360199

Language：Japanese  

The SDPA (SemiDefinite Programming Algorithm) on the Ninf (A Network based Information Library for the Global Computing)
In resent years, semidefinite program(SDP)has been intensively studied both in theoretical and practical aspects of various fields including interior-point methods, combinatorial optimization and the control and systems theory. The SDPA(SemiDefinite Programming Algorithm)[1]is an optimization software, implemented by C++ language, of a Mehrotra-type primal-dual predictor-corrector interior-point method for solving the standard form semidefinite program. In this paper, we also discuss parallel execution of the SDPA on the Ninf[3], a global network-wide computing infrastructure which has been developed for high-performance numerical computation services. We report some numerical results on a parallel implementation of the successive convex relaxation method proposed by Kojima and Tuncel[4]applying the SDPA on the Ninf.

Language：English  

The DMVT was developed systematically by using semidefinite programming algorithm (SDPA) as a problem solver. It was shown that the technique is very stable. Although errors were found, these are permissible in both energy and properties.

DOI： 10.1063/1.1360199

Language：Japanese  

OPTIMIZATION SYSTEM OF SUB-PACKAGE PROBLEM IN BUILDING CONSTRUCTION PROJECT USING MATHEMATICAL PROGRAMMING
This paper describes the sub-package problem in the building construction project which is defined to combine various resources under some constrained conditions and multipurpose. Multipurpose includes the term of works, the cost, the quality, the safety, and so on. Various resources include the labor, the material, and the temporary facilities and machinery, etc. The sub-package is currently arranged through the personal judgment of the site manager. However, this way of arrangement comes to the limitation. In this paper, the methods of the sub-package in construction firms are collected through interviews and surveys. Then, the decision-making support system of the sub-package is developed to achieve the optimization with mathematical programming model where the evaluation criteria are the overhead cost and the management time in sub-package problem.

DOI： 10.3130/aija.66.235_2

Language：Japanese  

Animating Graph Partition Algorithm

Language：Japanese  

Topology Optimization of Trusses for Specified Multiple Eigenvalue by using Semidefinite Programming
Algorithms based on Semi-Definite Programming (SDP) are proposed for the truss topology optimization problems for specified fundamental eigenvalue of free vibration and linear buckling load factor, and optimal topologies of trusses are computed by using the Semi-Definite Programming Algorithm (SDPA). It is well known that optimizing structures for specified minimum eigenvalue is difficult because of non-differentiability of the minimum eigenvalue for the cases of multimodal solutions. It is shown, in the examples, that the proposed algorithms are applicable to multimodal cases.

DOI： 10.1299/jsmeoptis.2000.4.151

Language：Japanese  

The SDPA (SemiDefinite Programming Algorithm) on the Ninf (A Network based Information Library for the Global Computing) (Mathematical Science of Optimization)

Language：English  

A Combinatorial Problem Arising from Polyhedral Homotopies for Solving Polynomial Systems (Mathematical Science of Optimization)

Language：English  

Solving Sparse Semidefinite Programs by Matrix Completion(Part 1) (Mathematical Science of Optimization)

Language：Japanese  

Multi-Project Scheduling with Discounted Cash Flows

Language：Japanese  

Development of a method for detecting vanishing points of an architectural image and reconstructing a 3D architectural model

Language：Japanese  

The Software of the Primal-Dual Interior-Point Method for Semidefinite Programming SPDA(SemiDefinite Programming Algorithm)

DOI： 10.11509/isciesci.44.2_51

Language：Japanese  

2033 Topology Optimization of Trusses for Specified Multiple Linear Buckling Load Factor by using Semidefinite Programming

Language：Japanese  

Language：Japanese  

Language：English  

Topology optimization problem of trusses for specified eigenvalue of vibration is formulated as Semi-Definite Programming (SDP), and an algorithm is presented based on the Semi-Definite Programming Algorithm (SDPA) which utilizes extensively the sparseness of the matrices. Since the sensitivity coefficients of the eigenvalues with respect to the design variables are not needed, the SDPA is especially useful for the case where the optimal design has multiple fundamental eigenvalues. Global and local modes are defined and a procedure is presented for generating optimal topology from the practical point of view. It is shown in the examples, that SDPA has advantage over existing methods in view of computational efficiency and accuracy of the solutions, and an optimal topology with five-fold fundamental eigenvalue is found without any difficulty. © 1999 Elsevier Science S.A.

DOI： 10.1016/S0045-7825(99)00056-0

Language：English  

Topology optimization problem of trusses for specified eigenvalue of vibration is formulated as Semi-Definite Programming (SDP), and an algorithm is presented based on the Semi-Definite Programming Algorithm (SDPA) which utilizes extensively the sparseness of the matrices. Since the sensitivity coefficients of the eigenvalues with respect to the design variables are not needed, the SDPA is especially useful for the case where the optimal design has multiple fundamental eigenvalues. Global and local modes are defined and a procedure is presented for generating optimal topology from the practical point of view. It is shown in the examples, that SDPA has advantage over existing methods in view of computational efficiency and accuracy of the solutions, and an optimal topology with five-fold fundamental eigenvalue is found without any difficulty.

DOI： 10.1016/S0045-7825(99)00056-0

Language：English  

Approximation of Optimal Two-Dimensional Association Rules for Categorical Attributes Using Semidefinite Programming
© Springer-Verlag Berlin Heidelberg 1999. We consider the problem of finding two-dimensional association rules for categorical attributes. Suppose we have two conditional attributes A and B both of whose domains are categorical, and one binary target attribute whose domain is {“positive”, “negative”}. We want to split the Cartesian product of domains of A and B into two subsets so that a certain objective function is optimized, i.e., we want to find a good segmentation of the domains of A and B. We consider in this paper the objective function that maximizes the confidence under the constraint of the upper bound of the support size. We first prove that the problem is NP-hard, and then propose an approximation algorithm based on semidefinite programming. In order to evaluate the effectiveness and efficiency of the proposed algorithm, we carry out computational ex- periments for problem instances generated by real sales data consisting of attributes whose domain size is a few hundreds at maximum. Approxi- mation ratios of the solutions obtained measured by comparing solutions for semidefinite programming relaxation range from 76&#37; to 95&#37;. It is observed that the performance of generated association rules are signifi- cantly superior to that of one-dimensional rules.

DOI： 10.1007/3-540-46846-3_14

Language：Japanese  

Semi-Definite Programming for Topology Optimization of Trusses under Multiple Eigenvalue Constraints

Language：English  

Maximizing Net Present Value for Generalized Resouece Constrained Project Scheduling Problem

Language：Japanese  

International Conference on Nonlinear Programming and Variational Inequalities(Conference Reports)

DOI： 10.11540/bjsiam.9.3_269_1

Language：English  

8025 Maximizing Net Present Value for Generalized Resource Constrained Project Scheduling Problem

Language：Japanese  

2019 Semi-Definite Programming for Topology Optimization of Trusses under Multiple Eigenvalue Constraints

Language：Japanese  

Using the Conjugate Gradient Method in Interior-points Methods for Semidefinite Programs

Language：Others  

In this paper, we present a variant of local search, namely the Life Span Method (LSM), for generic combinatorial optimization problems. The LSM can be seen as a variation of tabu search introduced by Glover [18, 19]. We outline applications of the LSM to several combinatorial optimization problems such as the maximum stable set problem, the traveling salesman problem, the quadratic assignment problem, the graph partitioning problem, the graph coloring problem, and the job-shop scheduling problem.

DOI： 10.1007/BF03167318

Language：English  

The Implementation of the Primal-Dual Interior-Point Method for the Semidefinite Programs and its Engineering Applications
In resent years, semidefinite program (SDP) has been intensively studies both in theoretical and practical aspects of various fields including interior-point method, combinatorial optimization and the control and systems theory. The SDPA (SemiDefinite Programming Algorithm) [4] is a C++ implementation of a Mehrotra-type primal-dual predictor-corrector interior-point method for solving the standard form semidefinite program. The SDPA incorporates data structures for handling sparse matrices and an efficient method proposed by Fujisawa et al. [5] for computing search directions when problems to be solved are large scale and sparse. Finally, we report numerical experiments of the SDP for the structural optimization under multiple eigenvalue constraints.

Language：English  

In this paper, we present a variant of local search, namely the Life Span Method (LSM), for generic combinatorial optimization problems. The LSM can be seen as a variation of tabu search introduced by Glover [18, 19]. We outline applications of the LSM to several combinatorial optimization problems such as the maximum stable set problem, the traveling salesman problem, the quadratic assignment problem, the graph partitioning problem, the graph coloring problem, and the job-shop scheduling problem.

DOI： 10.1007/BF03167318

Language：English  

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse. © 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

DOI： 10.1007/BF02614319

Language：English  

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse.

DOI： 10.1007/BF02614319

Language：Japanese  

Language：Japanese  

Language：Others  

Language：Japanese  

Language：English  

Experimental analysis of a semidefinite programming approach to the graph partitioning problem

Language：Japanese  

Language：Japanese  

Tabu Search with a Diversification Strategy for Job Shop Scheduling Problem

Language：English  

Fast Implementation and Experiments of n Queens' Problem

Language：English  

Parameter Optimization of the Tabu Search for the Maximum Clique Problem

Language：Others  

An Application of Tabu Search to the Graph Partitioning Problem and its Experimental Analysis
In this paper, we report on an application of tabu search to the graph partitioning problem which has applications on circuit board wiring and program segmentation. We discuss how to adapt tabu search to the graph partitioning problem and compare the performance with simulated annealing, another variant of local search incorporating randomized technique. Numerical experiments show that our algorithm dominates the simulated annealing algorithm in accuracy of solutions and speed on both uniform and geometric instances. In particular, our tabu search implementation works much better than the simulated annealing algorithm on structured (geometric) instances. We also investigate how to tune up our implementation and to optimize the various parameters via extensive numerical experiments.

DOI： 10.1541/ieejeiss1987.114.4_430

Language：Japanese  

Language：English  

An Approximate Algorithm for the Maximum Stable Set Problem

Language：Japanese  

Language：Japanese  

Language：Japanese  

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：2

Number of peer-reviewed articles in Japanese journals：0

Proceedings of International Conference Number of peer-reviewed papers：10

Proceedings of domestic conference Number of peer-reviewed papers：0

Type：Scientific advice/Review 

Type：Scientific advice/Review 

Type：Competition, symposium, etc. 

Number of participants：220

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：3

Number of peer-reviewed articles in Japanese journals：2

Proceedings of International Conference Number of peer-reviewed papers：7

Proceedings of domestic conference Number of peer-reviewed papers：1

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：2

Number of peer-reviewed articles in Japanese journals：4

Proceedings of International Conference Number of peer-reviewed papers：10

Proceedings of domestic conference Number of peer-reviewed papers：0

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Number of participants：150

researchmap

researchmap

コヒーレントイジングマシンの応用に関する研究

researchmap

コヒーレントイジングマシンの応用に関する研究

検索データを用いたヒト・モノのモビリティに関する数理モデルの構築と検証実験

researchmap

検索データを用いたヒト・モノのモビリティに関する数理モデルの構築と検証実験

グラフ解析と高性能計算を用いた多人数追跡に関する研究

大規模最適化に関する共同研究

ハーネス自働外観検査向けDeep Learningによる不良画像認識に関する研究

プローブデータ分析に関する共同研究

物流＆人流データ解析に関する共同研究

researchmap

グラフ理論を用いた大型施設動向シュミレーションに関する研究

researchmap

グラフ理論を用いた大型施設動向シュミレーションに関する研究

物流＆人流データ解析に関する共同研究

IoTに向けたデータ取得・管理技術の研究

路車協調システム（コネクティッドカー）向けCANデータ及び車載映像データに関する調査研究