超高速・安定計算研究室(Fast, exact and stable computation Lab.)

研究室公式ブログ (Lab's Offcial blog) 日本語 & English

超高速・安定計算研究室 : 終了

2014-03-22 22:30:34 | Weblog
以下の超高速・安定計算研究室は 2014年3月を持って終了となりました。よってこのブログも休止(廃止ではありません)します。


最適化手法とは様々な条件の下で最も良い答えを求める方法です。例えば企業経営においては人件費、輸送費、在庫管理費などの条件を考慮しながら利益を最大化することが求められています。しかし最適化問題はコンピュータやネットワークの高速化を上回るペースで複雑かつ多様化しており、最適化手法のアルゴリズム改良だけでなく大規模な計算設備での並列計算等も必要になっています。さらに最適化問題が大規模、複雑化したことによって数値計算によって得られる精度が悪化していくので、高速化だけではなく安定した解が得られることも同様に重要になってきています。
よって我々の研究室では、近年の情報技術の発展による高速計算の手法(マルチコア、クラスタ、グリッドなどの並列計算技術)と最新のアルゴリズム科学の分野での成果を融合させて、高速かつ安定に大規模最適化問題に対する解を求めるための研究を行っています。

○超高速・安定計算研究室(2007年4月~ 2014年3月)
所属: 中央大学理工学部経営システム工学科

SC12 : Technical Paper 採択論文

2012-09-06 22:46:23 | Weblog
著者: Katsuki Fujisawa, Toshio Endo, Hitoshi Sato, Makoto Yamashita, Satoshi Matsuoka, Maho Nakata
タイトル: High-Performance General Solver for Extremely Large-scale Semidefinite Programming Problems
概要:

Semidefinite Programming (SDP) is one of the most important problems in current research areas in optimization problems. It covers a wide range of applications such as combinatorial optimization, structural optimization, control theory, economics, quantum chemistry, sensor network location, data mining, etc. Solving extremely large-scale SDP problems has significant importance for the current and future applications of SDPs. In 1995, Fujisawa et al. started the SDPA Project aimed for solving large-scale SDP problems with numerical stability and accuracy. SDPA is one of pioneers' codes to solve general SDPs. SDPARA is a parallel version of SDPA on multiple processors and distributed memory, which 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 on combinatorial optimization and truss topology optimization, the new version of SDPARA(7.5.0-G) on a large-scale super computer called TSUBAME2.0 at Tokyo Institute of Technology has succeeded to solve the largest SDP problem which has over 1.48 million constraints and make a new world record. Our implementation has also achieved 533 TFlops in double precision for the large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs.

Important Links

2010-06-19 22:17:47 | Weblog

1: SDPA Project Home Page
2: SDPA Online Solver
3: The Shortest Path Online Solver
4: TOP Page (日本語), (English)

World Record in Computational Quantum Chemistry

2010-05-29 12:46:17 | Weblog
Fujitsu Supercomputer Achieves World Record in Computational Quantum Chemistry

Solves optimization problem to reveal the behavior of 3 key molecules, contributes to research in science and technology

Tokyo, May 28, 2010 ― Fujitsu Limited and Chuo University of Japan today announced that a team of researchers(1) from Chuo University, Kyoto University, Tokyo Institute of Technology and Japan's Institute of Physical and Chemical Research (known as Riken) employed the T2K Open Supercomputer - which was delivered by Fujitsu to Kyoto University's Academic Center for Computing and Media Studies - to successfully compute with high precision, as a world first, an optimization problem to reveal the molecular behavior of ethane (CH3), ammonia (NH3) and oxygen (O2).
This accomplishment paves the way for computing the behavior of complicated molecules that cannot be seen by the human eye, by enabling researchers to gain a greater understanding of the behavior of water molecules, the properties of proteins, photosynthesis, and the mechanisms of superconductivity would also contribute to the development of new medicines and new materials. Furthermore, a wide range of potential applications is expected to emerge from this research, not only in the fields of physics and chemistry, but also in engineering and social sciences areas such as natural sciences, control design and signal/image processing.

Results
The research team from Chuo University, led by Professor Katsuki Fujisawa, developed the SDPARA software package, based on an advanced optimization algorithm, as a high-speed SDP computational method. By running large-scale tests of SDPARA on the T2K Open Supercomputer, the team was successfully able for the first time ever to precisely compute the behavior of ethane (CH3), ammonia (NH3) and oxygen (O2).
During the actual computation, the matrix for the largest molecule employed in this study - ammonia (NH3) - reached a size of 19,640 × 19,640, and therefore had too many elements to be processed in a practical amount of time using average computer systems (Figure 3). By employing a supercomputer, the team was successfully able to solve the matrix in the computing time shown in Figure 4. For this computation, the T2K Open Supercomputer employed 128 nodes for its computations, utilizing a total memory volume of 4 terabytes and 2048 cores.

New technologies in the SDPA Project

2009-09-20 21:13:29 | Weblog
The SDPA Project started in 1995 have provided several software packages for solving large-scale Semidefinite Programs(SDPs). Further improvements are necessary for the software packages since optimization problems become larger and more complicated. We show some current works and new technologies in the SDPA project as follows; (I) The memory hierarchy is carefully considered to specify the bottleneck of the algorithm and improve the performance. The latest version of the SDPA supports the multi-thread computing on multi-core processor, and solves large-scale SDPs quickly and efficiently. (II) We have developed a web portal system utilizing the cloud computing technology for some software packages in the SDPA Project.
The PDF file of the presentation in ISMP 2009 is available from here.

SDPA 7.3.1 now available!! : 07/30/2009

2009-07-30 20:36:03 | Weblog
We have released the SDPA 7.3.1 ; [Download].

See new features of the SDPA 7.3.1 below;

* Introduce multi-thread computing
* Change data structures for input data matrices
* Add sedumiwrap.m (SeDuMi wrapper for SDPA-M) [For details, try 'help sedumiwrap' in Matlab after installation]
* Fix small bugs

Four types of solvers has been released!!

2009-03-21 20:54:33 | Weblog
We have released four software packages below; [Download].

* SDPA 7.3.0 (new version)
* SDPA-GMP 7.1.2 (updated)
* SDPA-QD 7.1.2 (new release)
* SDPA-DD 7.1.2 (new release)

The Report of the SDPA Project in August, 2008.

2008-09-19 17:54:19 | Weblog
The SDPA Project started in 1995 have provided several software packages for solving large-scale Semide nite Programs(SDPs). The SDPA 6.2.1 attained high performance for large-scale dense SDPs, however, it required much computation time compared with other software packages when the Schur complement matrix is sparse. The SDPA 7.1.1 is completely revised from its source code, and there are great performance improvements on its computation time and memory usage.
The objective of this paper is to present brief explanations of the SDPA 7.1.1 and its high performance for large-scale dense and sparse SDPs through numerical experiments compared with some other major software packages for general SDPs. We also review the major achievements of the SDPA Project on solving large-scale SDPs.
The PDF file of the presentation in SJOM 2008 is available from here.

The Shortest Path Online and GoogleMaps

2008-09-18 17:39:43 | Weblog
The Shortest Path Online is currently working in cooperation with the GoogleMaps. Users can input starting and ending points on the GoogleMaps. Note that inside points of the USA are only available, because we have only data files of the USA, which contain nodes, their coordinates and so on.
We have implemented the Dijkstra algorithm with heap and bucket data structure. The memory hierarchy is carefully considered to specify the bottleneck of the algorithm and improve the performance. This implementation can solve large-scale shortest path problem quickly.
The online solver can also display shortest paths on the GoogleMaps. The figure attached in this article shows two shortest paths. The red and blue paths denote the shortest paths to minimize the total distance and time between the starting and ending points, respectively.

New cluster computer is coming!!

2008-08-15 11:33:31 | Weblog
New computers which we call "SDPA cluster" is now in operation. The specification of the SDPA cluster is as follows;

16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.3 for x86_64
Linpack : R_max = 1.435TFlops, R_peak = 1.618TFlops, R_max / R_peak = 88.69%


The cluster is mainly aimed for developing and evaluating the software SDPARA and SDPA. We expect that it will break a wolrd record for solving extremely large-scale SDPs. We also have a plan to use it as computing resources of the SDPA Online Solver.