| 藤澤 克樹（ふじさわ かつき） | データ更新日：2024.04.09 |
教授 ／
マス・フォア・インダストリ研究所
数理計算インテリジェント社会実装推進部門
| 1. | 藤澤 克樹, ディジタルツインのための数理・情報技術と産業応用—Mathematical and Information Technologies for Digital Twin and Industrial Applications—小特集 接近するバーチャルとリアル : メタバース・ディジタルツインの現在と未来, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, Vol.106, No.8, pp.735-742, 2023.08. |
| 2. | 藤沢 克樹, 久保 幹雄, 森戸 晋, Tabu Searchのグラフ分割問題への適用と実験的解析, 電気学会論文誌. C, 10.1541/ieejeiss1987.114.4_430, Vol.114, No.4, pp.430-437, 1994.06, 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.. |
| 3. | 藤沢克樹, 組合せ最適化問題に対する近似解法, 第8回RAMPシンポジウム論文集, 1996, 1996.07. |
| 4. | 藤沢 克樹, 非線形最適化と変分不等式に関する国際会議(学術会合報告), 応用数理, 10.11540/bjsiam.9.3_269_1, Vol.9, No.3, p.269, 1999.06. |
| 5. | 寒野 善博, 大崎 純, 藤澤 克樹, 加藤 直樹, 半正定値計画法を用いた重複固有値を有するトラスのトポロジー最適化問題, 最適化シンポジウム講演論文集, 10.1299/jsmeoptis.2000.4.151, Vol.2000, No.0, pp.151-156, 2000.10, 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.. |
| 6. | 藤沢 克樹, 半正定値計画問題に対する内点法ソフトウェアSDPA(SemiDefinite Programming Algorithm), システム／制御／情報, 10.11509/isciesci.44.2_51, Vol.44, No.2, pp.51-58, 2000.06. |
| 7. | 山中 俊介, 加藤 直樹, 藤澤 克樹, 建築画像の消失点検出手法の開発とそれに基づく3次元建築モデルの再構成手法, 日本建築学会計画系論文集, 10.3130/aija.66.269_1, Vol.66, No.542, pp.269-277, 2001.12, 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.. |
| 8. | 勝山 典一, 古阪 秀三, 藤澤 克樹, 金多 隆, 建築生産情報の確定過程に関する研究, 日本建築学会計画系論文集, 10.3130/aija.66.223_5, Vol.66, No.548, pp.223-230, 2001.12, 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.. |
| 9. | 則武 譲二, 古阪 秀三, 藤澤 克樹, 金多 隆, 建築工事編成最適化システムの構築, 日本建築学会計画系論文集, 10.3130/aija.66.235_2, Vol.66, No.550, pp.235-242, 2001.04, 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.. |
| 10. | 植田 浩二, 古阪 秀三, 藤沢 克樹, 室谷 泰蔵, 金多 隆, 繰り返し型建築工事におけるTOCを用いた工程計画に関する研究, 日本建築学会計画系論文集, 10.3130/aija.67.281_4, Vol.67, No.557, pp.281-288, 2002.04, 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.. |
| 11. | 和田 祐考, 古阪 秀三, 藤澤 克樹, 金多 隆, 建築プロジェクトにおける工事編成最適化 : 工事編成支援システムの提案, 日本応用数理学会論文誌, 10.11540/jsiamt.12.1_9, Vol.12, No.1, pp.9-28, 2002.04, 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.. |
| 12. | Akiko Takeda, Katsuki Fujisawa, Yusuke Fukaya, Masakazu Kojima, Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems, Journal of Global Optimization, Vol.24, No.2, pp.237-260, 2002.06. |
| 13. | Takeda Akiko, Kojima Masakazu, Fujisawa Katsuki, ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD, 日本オペレーションズ・リサーチ学会論文誌, 10.15807/jorsj.45.64, Vol.45, No.1, pp.64-82, 2002.04, 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.. |
| 14. | 宮高 泰匡, 加藤 直樹, 藤沢 克樹, ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関関係の分析, 日本建築学会環境系論文集, 10.3130/aije.68.133, Vol.68, No.568, pp.133-140, 2003.10, 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.. |
| 15. | Fujisawa Katsuki, Kojima Masakazu, Takeda Akiko, Yamashita Makoto, SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING( |
| 16. | Katsuki Fujisawa, Masakazu Kojima, Akiko Takeda, Makoto Yamashita, High performance grid and cluster computing for some optimization problems, Proceedings - International Symposium on Applications and the Internet Workshops, pp.612-615, 2004.09, 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.. |
| 17. | 藤澤 克樹, 実務的な大規模最適化問題に対する並列メタ戦略アルゴリズムの開発, 総合研究所年報, No.25, pp.183-188, 2005.04. |
| 18. | 古阪 秀三, 金多 隆, 加藤 直樹, 藤澤 克樹, 水野 隆介, 庁舎建築の企画・設計におけるコストプランニングシステムに関する研究(建築経済・住宅問題), 日本建築学会技術報告集, 10.3130/aijt.12.437, Vol.12, No.23, pp.437-442, 2006.04, 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.. |
| 19. | 藤澤 克樹, 半正定値計画問題の使い方とソルバーの性能について, システム制御情報学会 研究発表講演会講演論文集, 10.11509/sci.SCI10.0.320.0, Vol.10, No.0, p.320, 2010.05, 半正定値計画問題 (以下 SDP) は現在非常に注目されている数理計画問題であり，21世紀の線形計画問題としての役割を期待されている．しかし，最適化以外の専門分野では SDP の問題記述能力やソルバーの特性，性能などの最新の情報は知られていないことも多い．そこで本講演においては以下の項目について解説を行う．1. SDP の問題記述＆解決能力 (問題の変換や記述方法等)2. SDP ソルバーの紹介 (各ソルバーの特徴や使い方等)3. SDP ソルバーの性能 1: 高速＆大規模計算 (解くことができる SDP の問題規模と計算時間について)4. SDP ソルバーの性能 2: 高精度＆安定計算 (数値精度の問題と解決法，任意精度計算等)5. SDP ソルバーの開発における最新技術について. |
| 20. | 安井 雄一郎, 藤澤 克樹, 笹島 啓史, 後藤 和茂, 大規模最短路問題に対するダイクストラ法の高速化, 日本オペレーションズ・リサーチ学会和文論文誌, 10.15807/torsj.54.58, Vol.54, No.0, pp.58-83, 2011.04, 最短路問題はネットワーク上の経路探索などの多くの応用を持ち,また他の最適化問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.最短路問題に対する解法としてはダイクストラ法などの安定的かつ効率的な高速アルゴリズムが存在するが,実問題は非常に大規模になるためさらなる高速化が不可欠である.そこで本論文では大規模最短路問題に対し,計算機のメモリ階層構造を考慮しつつ汎用的かつ効率的に高速化を行うための実装方法を示す.さらに論文中では計算機のメモリ階層構造における律速箇所の特定を行うための汎用的な解析方法を示し,高速化の有用性を検証していく.本手法により実装されたバイナリ・ヒープを適用したダイクストラ法は,実行性能,安定性,メモリ要求量などを他の実装と比較すると総合的に最も優れているといえる.また本実装を用いた大規模最短路問題に対するオンライン・ソルバーについても説明を行う.. |
| 21. | Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazuhide Nakata, Maho Nakata, Latest developments in the SDPA family for solving large-scale SDPs, International Series in Operations Research and Management Science, 10.1007/978-1-4614-0769-0_24, Vol.166, pp.687-713, 2012.10. |
| 22. | 藤澤 克樹, 大規模グラフ解析と避難シミュレーションへの応用, 人工知能学会全国大会論文集, 10.11517/pjsai.JSAI2014.0_1C5OS13b1, Vol.2014, No.0, p.1C5OS13b1, 2014.05, スーパーコンピュータを用いた超大規模なグラフ最適化技術，およびその社会応用の例として，緊急避難シミュレーションを紹介する． . |
| 23. | 小林 和博, 成澤 龍人, 安井 雄一郎, 藤澤 克樹, 辞書式最速流による避難計画作成モデルの実験的解析, 日本オペレーションズ・リサーチ学会和文論文誌, 10.15807/torsj.59.86, Vol.59, No.0, pp.86-105, 2016.06, 津波発生時には，浸水対象の地域にいる住民はできるだけ迅速に避難する必要がある．本論文では，浸水域にいる要避難者が効率的に避難するための避難計画を，動的ネットワークフローモデルを用いて求める方法を扱う．特に，避難場所に容量制約がある場合に有効なモデルを扱う．具体的には，要避難者の避難状況を動的ネットワーク上の動的フローとして表現し，効率的な避難計画を辞書式最速流として定式化する．そして，この辞書的最速流を求めるアルゴリズムの実験的解析を，実際の地理情報に基づいて実施する． . |
| 24. | 藤澤 克樹, Mathematical Software – ICMS 2016—5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings, Lecture Notes in Computer Science, 10.1007/978-3-319-42432-3, 2016.06. |
| 25. | 藤澤克樹, ポストペタスケールシステムにおける超大規模グラフ最適化基盤, 戦略的創造研究推進事業CREST終了報告書(Web), Vol.2016, p.WEB ONLY, 2017.04. |
| 26. | 藤澤 克樹, Performance evaluation of Graph500 considering CPU-DRAM power shifting, SC17 Regular, Electronic, and Educational Poster, International Conference for High Performance Computing, Networking, Storage and Analysis 17 (SC17), Vol.-, 2017.11. |
| 27. | 秦 希望, 西川 由理, 中山 俊, 小澤 順, 藤澤 克樹, K-Shortest Pathsを用いた多人数追跡におけるデータ削減による高速化, 人工知能学会全国大会論文集, 10.11517/pjsai.JSAI2018.0_2D103, Vol.2018, No.0, p.2D103, 2018.10, 動体の追跡は困難かつ近年飛躍的に精度が向上してきている問題の１つである. 本論文では並列化された多人数追跡システムを提案する. 追跡においては, 動体検知及びIDの整合性の２つの問題が考えられる. Jeromeらはこれらの問題をK-Shortest Paths(KSP)を用いて解決し, 高精度な多人数追跡を実現した. しかしこの方法では追跡にあたって枝長を変化させながら最短路を繰り返し求めており, 並列化が困難である. そこで私たちは, KSPに用いられるProbability Occupancy Map(POM)というデータを用いてKSPの適用範囲を分割した. 結果として, 従来のKSPと比較して87%の精度を保ちつつ5.4倍の高速化を実験的に示すことに成功した. . |
| 28. | 立岩 斉明, 秦 希望, 田中 智, 吉田 明宏, 若松 孝, 中山 俊, 藤澤 克樹, Hybrid Vehicle Control and Optimization with a New Mathematical Method, 自動制御連合講演会講演論文集, 10.11511/jacc.61.0_1792, Vol.61, No.0, pp.1792-1799, 2018.09. |
| 29. | 石川 裕, 佐藤 三久, 今村 俊幸, 中尾 昌広, 児玉 祐悦, 工藤 周平, 似鳥 啓吾, 伊奈 拓也, 上野 晃司, 藤澤 克樹, 清水 俊幸, 三吉 郁夫, 三輪 英樹, 細井 聡, スーパコンピュータ「富岳」4冠達成—Feat of Winning Four Major Benchmarks on Supercomputer Fugaku, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, Vol.103, No.12, pp.1217-1220, 2020.12. |
| 30. | 田中, 智, 韓, 燦洙, 高橋, 健志, 藤澤, 克樹, 遺伝的アルゴリズムに基づいた広域スキャンのフィンガープリント特定技術の提案, コンピュータセキュリティシンポジウム2021論文集, pp.349-356, 2021.10, インターネット上の到達可能かつ未使用の IP アドレス空間（ダークネット）を利用し，新興のマルウェア活動を検知することは，迅速なサイバーセキュリティ対策を行うために必要不可欠である．しかし，巧妙な攻撃者による分散スキャンと調査目的スキャンを区別することは非常に難しい．既存研究では，スキャン対象のポートや送信元ホストの分布に着目することで，攻撃者によるスキャン活動の検知を試みているが，緻密に組織化されたスキャン活動の特定には至っていない．一方，スキャンパケットには他の通信と区別するための特徴（フィンガープリント）が埋め込まれていることが既存研究で知られている．本稿ではフィンガープリントを論理式で表現し，遺伝的アルゴリズムを応用することで，複雑な特徴（論理式）を捉える手法を初めて提案する．ダークネットトラフィックを用いた実験では，既存及び未知の論理式の特定に成功した．論理式を満たすパケットを分析することで，複数の脆弱性を狙った複数ホストによるスキャン活動を確認するとともに，それらは中規模以下のスキャナ郡によって行われることを確認した． Detection of malware activities using darknet traffic is essential to perform prompt cybersecurity measures. However, distributed malware scans are indistinguishable from scan activities for investigative purposes. On the other hand, existing research has revealed that scan packets have their identifier to specify their scan packets from other traffic data. Therefore, this paper represents an identifier as a boolean formula and specifies the identifier based on the genetic algorithm, which is the first research to the best of our knowledge. Numerical experiments using darknet traffic revealed both existing and unknown boolean formulas. We also confirmed some middle- or low-rate port scans targeting multiple vulnerabilities by analyzing packets satisfying the boolean formulas.. |
| 31. | 藤澤 克樹, 大規模グラフ解析の高速計算と実社会への応用—High-performance Computing for Large-scale Graph Analysis and Its Application to the Real World, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, Vol.104, No.4, pp.360-366, 2021.04. |
| 32. | FUJISAWA Katsuki, ENDO Toshio, 1-F-5 Peta-scale General Solver for Semidefinite Programming : Extremely Large-scale Parallel Cholesky Solver, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2014, pp.104-105, 2014.03. |
| 33. | 藤沢 克樹, 森戸 晋, グラフ分割問題に対するTabu Searchの数値実験(グラフ・ネットワーク(2)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.1992, pp.62-63, 1992.09. |
| 34. | 久保 幹雄, 藤沢 克樹, 吉川 明男, 森戸 晋, An Approximate Algorithm for the Maximum Stable Set Problem, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.1993, pp.162-163, 1993.10. |
| 35. | 藤沢 克樹, Tabu Searchアルゴリズムの組合せ最適化問題への適用, オペレーションズ・リサーチ : 経営の科学, Vol.39, No.1, pp.46-47, 1994.01. |
| 36. | 山越 康裕, 高山 裕志, 藤沢 克樹, 今泉 淳, Tabu Search with a Diversification Strategy for Job Shop Scheduling Problem(スケジューリング(2)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.1994, pp.182-183, 1994.10. |
| 37. | 藤沢 克樹, 久保 幹雄, 森戸 晋, Parameter Optimization of the Tabu Search for the Maximum Clique Problem, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.1994, pp.54-55, 1994.10. |
| 38. | 久保 幹雄, 藤沢 克樹, 森戸 晋, Fast Implementation and Experiments of n Queens' Problem, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.1994, pp.124-125, 1994.10. |
| 39. | 久保 幹雄, 藤沢 克樹, 森戸 晋, Experimental analysis of a semidefinite programming approach to the graph partitioning problem, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.1995, pp.244-245, 1995.03. |
| 40. | 下村 雅彦, 藤沢 克樹, 森戸 晋, 久保 幹雄, Clusteringによるグラフ分割問題へのメタ解法(グラフ・ネットワーク(2)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.1995, pp.246-247, 1995.03. |
| 41. | 古屋 貴行, 藤江 哲也, 藤沢 克樹, 小島 政和, 最大カット問題に対するSemidefinite Programming緩和(数理計画(2)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.1996, pp.202-203, 1996.05. |
| 42. | 藤沢 克樹, 半正定値計画(SDP)に対する内点法プログラムの数値実験(線型行列不等式と半正定値計画法), 数理解析研究所講究録, Vol.1004, No.1004, pp.190-199, 1997.06. |
| 43. | 宇野 毅明, 藤沢 克樹, 久保 幹雄, ロジスティクスにおける最適化ツールの開発(交通・輸送(2)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.1997, pp.84-85, 1997.04. |
| 44. | Katsuki Fujisawa, Masakazu Kojima, Kazuhide Nakata, Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Mathematical Programming, Series B, 10.1007/BF02614319, Vol.79, No.1-3, pp.235-253, 1997.10, 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.. |
| 45. | 藤沢 克樹, 半正定値計画問題(SDP)に対する主双対内点法の実装と工学的応用について, 情報処理学会研究報告. AL, アルゴリズム研究会報告, Vol.64, No.78, pp.9-16, 1998.09, 近年, 半正定値計画問題(SDP)は理論と実用の両面において, 内点法や組合せ最適化, 及び制御理論などの様々な分野で研究されている.SDPA[4]はC++言語で記述されたSDPの標準形を解く主双対内点法のソフトウェアである.SDPAは疎行列を扱うためのデータ構造と, 解くべき問題が大規模で疎構造を持つときに探索方向を効率良く計算する方法[5]を備えている.最後に複数の固有値制約下での構造最適化へのSDPの応用と数値実験結果を報告する.. |
| 46. | 中田 和秀, 藤沢 克樹, 小島 政和, 半正定値計画問題に対する主双対内点法における共役勾配法の実装, 統計数理 = Proceedings of the Institute of Statistical Mathematics, Vol.46, No.2, pp.297-316, 1998.12, 要旨あり計算と最適化原著論文. |
| 47. | Mikio Kubo, Katsuki Fujisawa, The life span method - A new variant of local search, Japan Journal of Industrial and Applied Mathematics, 10.1007/BF03167318, Vol.15, No.3, pp.363-393, 1998.10, 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.. |
| 48. | 寒野 善博, 藤澤 克樹, 大崎 純, 加藤 直樹, 半正定値計画法を用いた構造最適設計 (最適化のための連続と離散数理), 数理解析研究所講究録, Vol.1114, No.1114, pp.139-148, 1999.11. |
| 49. | M. Ohsaki, K. Fujisawa, N. Katoh, Y. Kanno, Semi-definite programming for topology optimization of trusses under multiple eigenvalue constraints, Computer Methods in Applied Mechanics and Engineering, 10.1016/S0045-7825(99)00056-0, Vol.180, No.1-2, pp.203-217, 1999.11, 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.. |
| 50. | 藤沢 克樹, 羽室 行信, 加藤 直樹, Approximation of Optimal Two-Dimensional Association Rules for Categorical Attributes Using Semidefinite Programming, 人工知能基礎論研究会, 10.1007/3-540-46846-3_14, Vol.1721, No.37, pp.137-142, 1999.07. |
| 51. | 後藤 英司, 加藤 直樹, 藤沢 克樹, 上甲 武司, 8048 キャッシュフローを考慮した一般化資源制約付きプロジェクトスケージューリング問題に関する研究, 学術講演梗概集. F-1, 都市計画, 建築経済・住宅問題, Vol.1999, pp.1135-1136, 1999.07. |
| 52. | 藤沢 克樹, 後藤 英司, 加藤 直樹, 上甲 武司, 8025 キャッシュフローを考慮した一般化資源制約付きプロジェクトスケジューリング問題に関する研究(建築経済・住宅問題), 日本建築学会近畿支部研究報告集. 計画系, No.39, pp.897-900, 1999.05. |
| 53. | 寒野 善博, 藤澤 克樹, 大崎 純, 加藤 直樹, 20190 半正定値計画法を用いた重複固有振動数を有するトラスのトポロジー最適化, 学術講演梗概集. B-1, 構造I, 荷重・信頼性,応用力学・構造解析,基礎構造,シェル・立体構造・膜構造, Vol.1999, No.1999, pp.379-380, 1999.07. |
| 54. | 寒野 善博, 加藤 直樹, 大崎 純, 藤澤 克樹, 2019 半正定値計画法を用いた指定1次固有振動数を有するトラスのトポロジー最適化(構造), 日本建築学会近畿支部研究報告集. 構造系, No.39, pp.101-104, 1999.05. |
| 55. | 藤澤 克樹, 武田 朗子, 小島 政和, 中田 和秀, 半正定値計画問題に対するソフトウェアSDPAの広域並列計算システム (Mathematical Science of Optimization), 数理解析研究所講究録, Vol.1174, No.1174, pp.138-145, 2000.10. |
| 56. | 福田 光浩, 中田 和秀, 藤澤 克樹, 小島 政和, 室田 一雄, Solving Sparse Semidefinite Programs by Matrix Completion(Part 1) (Mathematical Science of Optimization), 数理解析研究所講究録, Vol.1174, No.1174, pp.122-129, 2000.10. |
| 57. | 藤沢 克樹, SDPA(半正定値計画問題に対するソフトウェア), オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.45, No.3, pp.125-131, 2000.03. |
| 58. | 武田 朗子, 小島 政和, 藤澤 克樹, A Combinatorial Problem Arising from Polyhedral Homotopies for Solving Polynomial Systems (Mathematical Science of Optimization), 数理解析研究所講究録, Vol.1174, No.1174, pp.146-158, 2000.10. |
| 59. | 上甲 武司, 加藤 直樹, 古阪 秀三, 藤沢 克樹, 8114 キャッシュフローを考慮した複数プロジェクトスケジューリング, 学術講演梗概集. F-1, 都市計画, 建築経済・住宅問題, Vol.2000, No.2000, pp.1307-1308, 2000.07. |
| 60. | 寒野 善博, 大崎 純, 藤澤 克樹, 加藤 直樹, 2033 半正定値計画法を用いた指定座屈荷重係数を有するトラスのトポロジー最適化(構造), 日本建築学会近畿支部研究報告集. 構造系, No.40, pp.145-148, 2000.05. |
| 61. | 山中 俊介, 加藤 直樹, 藤沢 克樹, 11009 建築画像の消失点検出手法の開発とそれに3次元建築モデルの再構成手法, 学術講演梗概集. A-2, 防火,海洋,情報システム技術, Vol.2000, No.2000, pp.403-404, 2000.07. |
| 62. | 藤沢 克樹, 建築生産分野における最適化(統合オペレーション), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2001, pp.12-13, 2001.05. |
| 63. | 藤沢 克樹, 武田 朗子, 小島 政和, 中田 和秀, 広域分散コンピューティング環境における数理計画ソフトウェアSDPA, 情報処理学会研究報告. HPC,[ハイパフォーマンスコンピューティング], Vol.86, No.49, pp.31-36, 2001.05, 近年, 半正定値計画法は数理計画法の分野において理論的研究がさかんに行われている.また同時に組合せ最適化, システムと制御理論, データマイニングなどの応用分野も同時に研究が行われている.著者らは, 半正定値計画問題を解くための主双対内点法を実現したソフトウェアSDPA[1]の開発を行い, 数値実験によって有効性の検証を行ってきた.本研究では, 広域分散コンピューティング環境であるNinf[3]を用いてSDPAの並列化を行い, 数理計画問題の中でも難しい範疇に属する非凸最適化問題を解くことを試みる.. |
| 64. | Maho Nakata, Hiroshi Nakatsuji, Masahiro Ehara, Mitsuhiro Fukuda, Kazuhide Nakata, Katsuki Fujisawa, Variational calculations of fermion second-order reduced density matrices be semidefinite programming algorithm, Journal of Chemical Physics, 10.1063/1.1360199, Vol.114, No.19, pp.8282-8292, 2001.05, 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.. |
| 65. | 加藤 直樹, 藤沢 克樹, TD-1-1 目で見るグラフ分割アルゴリズム, 電子情報通信学会総合大会講演論文集, Vol.2001, No.1, pp.298-299, 2001.03. |
| 66. | 武田 朗子, 小島 政和, 藤沢 克樹, 多面体ホモトピー法から生じる条件付き線形不等式系の全解列挙法, オペレーションズ・リサーチ : 経営の科学, Vol.47, No.3, p.190, 2002.03, 1995年に多面体ホモトピー法が提案されて以来,多項式方程式系の全根列挙問題に関する研究は飛躍的に発展してきた.多面体ホモトピー法はそれまでのホモトピー法に比べて計算量が少なく済むという素晴らしい性質を持つ反面,ホモトピー法に必要な"初期方程式系"を形成するために「条件付き線形不等式系に対する全解列挙」という新たな組合せ問題が生じてしまう.現在,多項式方程式系の全根列挙に必要な計算時間の約3分の1が,この組合せ問題を解くことに費されており,この部分の高速化が望まれている.本論文では,条件付き線形不等式系の全解列挙問題に対して,線形計画法の感度分析テクニック,双対理論を使ったアルゴリズムを提案する.また,本アルゴリズムに対して効率の良い並列計算処理が可能であり,並列計算機に実装した結果,今まで解けなかった規模の問題まで扱えるようになった.本アルゴリズムの必要とする計算機メモリーや計算時間などを既存の実験結果と比べることにより,その有効性を検証する.. |
| 67. | 藤沢 克樹, High Performance Grid Computing for Optimization Problem〔和文〕 (最適化の数理とアルゴリズム研究集会報告集), 数理解析研究所講究録, Vol.1297, No.1297, pp.192-199, 2002.12. |
| 68. | 宮高 泰匡, 加藤 直樹, 藤沢 克樹, 11022 ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関分析, 学術講演梗概集. 構造系, Vol.2002, No.2, pp.485-486, 2002.08. |
| 69. | 山下 真, 藤沢 克樹, 小島 政和, 半正定値計画問題を解くソフトウェアのPCクラスタ上における並列実装(最適化(2)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2003, pp.128-129, 2003.03. |
| 70. | 藤沢 克樹, 半正定値計画問題に対するソフトウェア, 電子情報通信学会誌, Vol.86, No.10, pp.777-779, 2003.10. |
| 71. | M. Yamashita, K. Fujisawa, M. Kojima, SDPARA: Semidefinite programming algorithm paRAllel version, Parallel Computing, 10.1016/S0167-8191(03)00087-5, Vol.29, No.8, pp.1053-1067, 2003.08, 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.. |
| 72. | Makoto Yamashita, Katsuki Fujisawa, Masakazu Kojima, Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0), Optimization Methods and Software, 10.1080/1055678031000118482, Vol.18, No.4 II, pp.491-505, 2003.08, 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.. |
| 73. | Kazuhide Nakata, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results, Mathematical Programming, Series B, 10.1007/s10107-002-0351-9, Vol.95, No.2, pp.303-327, 2003.02, 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.. |
| 74. | 藤澤 克樹, 大規模最適化問題への挑戦 -クラスタ＆グリッド計算の適用例について-, 情報処理, Vol.45, No.4, pp.372-376, 2004.04, 最適化問題は非常に広い応用範囲を持っているが，実用的なレベルでは問題サイズが大きくなり，必要な計算量も問題サイズに対して指数的に増加していくのでアルゴリズムの改良だけでなく，大規模な計算設備での並列計算も必要になる．本稿では大規模計算問題として最適化問題を取り上げ，組合せ最適化問題や数理計画問題になどに対する最新の並列計算（グリッドやクラスタ計算なども含む）の手法とその成果，また具体的な事例について解説を行う．. |
| 75. | 中田 和秀, 山下 真, 藤沢 克樹, 小島 政和, 半正定値計画に対する行列補完型主双対内点法の並列化(錘計画問題と相補正問題), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2004, pp.10-11, 2004.03. |
| 76. | 久保 幹雄, 藤澤 克樹, グリッド技術を用いたサプライ・チェイン最適化システム, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.49, No.12, pp.763-770, 2004.12. |
| 77. | T Gunji, S Kim, M Kojima, A Takeda, K Fujisawa, T Mizutani, PHoM - a polyhedral homotopy continuation method for polynomial systems, COMPUTING, 10.1007/s00607-003-0032-4, Vol.73, No.1, pp.57-77, 2004.07, 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.. |
| 78. | 藤澤 克樹, 半正定値計画問題(SDP)に対するソフトウェアと超大規模計算(ここまで使える数理計画法), シンポジウム, No.56, pp.11-32, 2006.09, 大規模最適化問題を解くための試みは様々な分野で行われているが,実用的なレベルで問題を解くためにはアルゴリズムの改良だけでなく,最新の情報技術を駆使して大規模な計算基盤上で並列計算を行うことも必要である.本解説では大規模最適化問題として半正定値計画問題(SDP)とSDPを解くためのソフトウェアSDPAを取り上げ,SDPの定義,例題や利用法などを簡単に説明した後で,SDPAで採用したアルゴリズム,超大規模なSDPに対する数値実験結果,クラスタ&グリッド技術を用いたSDPA Online Solverなどについて解説を行う.. |
| 79. | Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuhide Nakata, Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs, Parallel Combinatorial Optimization, 10.1002/9780470053928.ch9, pp.211-238, 2006.04. |
| 80. | T. Gunji, S. Kim, K. Fujisawa, M. Kojima, PHoMpara - Parallel implementation of the polyhedral homotopy continuation method for polynomial systems, Computing (Vienna/New York), 10.1007/s00607-006-0166-2, Vol.77, No.4, pp.387-411, 2006.06, 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.. |
| 81. | Kazuhide Nakata, Makoto Yamashita, Katsuki Fujisawa, Masakazu Kojima, A parallel primal-dual interior-point method for semidefinite programs using positive definite matrix completion, Parallel Computing, 10.1016/j.parco.2005.07.002, Vol.32, No.1, pp.24-43, 2006.01, 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.. |
| 82. | 藤澤 克樹, 最適化問題に対する並列計算技術の適用, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.52, No.10, pp.627-632, 2007.10, 数年前からクラスタやグリッドなどの並列計算技術が広く普及し,多くの分野に適用されて成功を収めている.最近ではマルチコアを搭載したプロセッサの登場によって,さらに簡単,安価に並列計算の適用が行えるようになった.本稿では最適化問題をめぐる並列計算技術の現状に触れた後,最適化問題として半正定値計画問題を取り上げ,並列計算の適用に関する実験結果と考察等を報告する. |
| 83. | Xiao Qing Bai, Hua Wei, Katsuki Fujisawa, Solution of optimal power flow problems by semi-definite programming, Zhongguo Dianji Gongcheng Xuebao/Proceedings of the Chinese Society of Electrical Engineering, Vol.28, No.19, pp.56-64, 2008.07, 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.. |
| 84. | 藤澤 克樹, 小島 政和, 中田 和秀, 福田 光浩, 山下 真, 中田 真秀, SDPA project and new features of SDPA 7.1.0 (計算科学の基盤技術としての高速アルゴリズムとその周辺--RIMS研究集会), 数理解析研究所講究録, Vol.1614, No.1614, pp.136-143, 2008.10. |
| 85. | 安井 雄一郎, 藤澤 克樹, 笹島 啓史, 後藤 和茂, 宮本 裕一郎, 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2008, pp.314-315, 2008.09. |
| 86. | 福田 光浩, 中田 真秀, BRAAMS Bastiaan J., 藤澤 克樹, PERCUS Jerome K., 山下 真, ZHAO Zhengji, 2-D-6 半正定値計画による分子の電子構造計算(数理計画(1)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2008, pp.174-175, 2008.03. |
| 87. | 藤澤 克樹, 山下 真, 中田 和秀, 後藤 和茂, 2-D-14 最適化問題用オンライン・ソルバーの構築と自動選択機能の開発(非線形計画(3)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2008, pp.256-257, 2008.09. |
| 88. | 宮本 裕一郎, 藤澤 克樹, 久保 幹雄, 最短路検索, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.54, No.11, pp.700-703, 2009.11. |
| 89. | 藤澤 克樹, 宮本 裕一郎, 久保 幹雄, 最短路問題, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.54, No.11, pp.696-699, 2009.11. |
| 90. | 福田 光浩, 中田 和秀, 藤澤 克樹, 山下 真, 2-G-2 重み付き対数行列式を持つ半正定値計画問題を解くSDPA(連続最適化(1)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2009, pp.259-260, 2009.09. |
| 91. | 藤澤 克樹, 2-A-15 アルゴリズムサイエンス分野における最適化ソフトウエアの実装方式(計算と最適化(3)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2009, pp.138-139, 2009.03. |
| 92. | 久野 誉人, 村松 正和, 藤澤 克樹, 1-A-7 計算と最適化の新展開に向けて(計算と最適化(1)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2009, pp.18-19, 2009.03. |
| 93. | 安井 雄一郎, 藤澤 克樹, 笹島 啓史, 高宮 安仁, 後藤 和茂, 1-A-5 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化(つくばOR学生発表(5)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2009, pp.14-15, 2009.03. |
| 94. | 藤澤 克樹, 高速化・最適化のためのBLAS入門, 数学セミナー, Vol.49, No.9, pp.50-55, 2010.09. |
| 95. | 藤澤 克樹, 特集にあたって, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.55, No.7, p.386, 2010.07. |
| 96. | 藤澤 克樹, 最適化ソルバー開発への最新の情報技術の適用について, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.55, No.7, pp.418-424, 2010.07, 最適化ソフトウェアに関連性の高い情報技術には,マルチコア・プロセッサ,GPUコンピューティング,スーパーコンピュータ,クラウド・コンピューティングなどがある.これらの新技術が個別あるいは複合して最適化ソフトウェアとどのように絡んでくるのか,あるいはどのように活用すれば性能向上などの成果を上げることができるのかについては,最新の研究成果を含めてあまり知られていない.そこで本解説では,著者らのグループによる半正定値計画問題(SDP)に対するソフトウェア開発を題材にして,最先端の最適化アルゴリズムと最新の情報技術の有機的な融合方法等について触れていく.. |
| 97. | 藤澤 克樹, 大規模最適化問題に対する高速計算--理論からスパコンまで, 数学セミナー, Vol.49, No.10, pp.58-63, 2010.10. |
| 98. | 安井 雄一郎, 高宮 安仁, 藤澤 克樹, 大規模最短路問題に対する高速処理システム--メモリ階層構造の考慮とクラスタ&クラウド技術による高速化 (21世紀の数理計画--アルゴリズムとモデリング--RIMS研究集会報告集), 数理解析研究所講究録, Vol.1676, No.1676, pp.51-65, 2010.04. |
| 99. | 藤澤 克樹, 半正定値計画問題に対するソフトウェア開発で用いられる新技術について (21世紀の数理計画--アルゴリズムとモデリング--RIMS研究集会報告集), 数理解析研究所講究録, Vol.1676, No.1676, pp.16-27, 2010.04. |
| 100. | Maho Nakata, Mituhiro Fukuda, Katsuki Fujisawa, Variational approach for the electronic structure calculation on the second-order reduced density matrices and the $N$-representability problem, 2010.10, 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.. |
| 101. | 後藤 順哉, 藤澤 克樹, 2-B-8 決定係数最大化ポートフォリオ選択に対する凸最適化アプローチ(連続最適化), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2010, pp.130-131, 2010.03. |
| 102. | 高宮 安仁, 田浦 健次朗, 安井 雄一郎, 藤澤 克樹, "Bare Metal" Cloud : 実マシンを提供するクラウドサービス, 情報処理学会研究報告. [ハイパフォーマンスコンピューティング], Vol.126, No.39, pp.m1-m8, 2010.08, オンデマンドで仮想マシン (VM) を提供する Infrastructure as a Service (IaaS) は VM のオーバーヘッドや他のユーザが実行するジョブの影響により、大部分の HPC アプリケーションで本来の性能を出すことができない。VM のかわりに実マシンを提供する IaaS を実現すればこうした問題は解決できるが、VM イメージを元に何台でも複製できるという VM の高い運用性を実マシン上で実現するのは難しい。我々のシステムは 1) IaaS のデファクトスタンダードである Amazon EC2 の VM イメージを実マシンにインストールする仕組みと、2) インストールエラーの検出およびフェイルオーバー機能を備えることで、VM イメージを元に実マシンを安定してセットアップできる IaaS を実現した。これによって、HPC アプリケーションの性能を損ねない多様な実行環境を実マシン上に簡単にセットアップできる。Infrastructure as a Service (IaaS) that enables on-demand deployment of virtual machines (VM) cannot bring out the real performance of most of HPC applications because of the overhead of underlying VMs and the effect of other co-located users' activities. While real-machine based IaaS instead of VMs may settle these problems, it is still difficult to achieve high managability of VMs on real machines. Our novel mechanism achieved an IaaS that can deploy dedicated real machines on demand by providing follwoing mechanisms that: 1) install the VM image of Amazon EC2, the de-facto standard of IaaS, into real machines 2) failover boot errors by investigating boot-sequence syslogs. With these mechanisms, one can build a variety of execution environments that never lower the performance of HPC applications on real machines.. |
| 103. | 安井 雄一郎, 藤澤 克樹, 佐藤 仁, 鈴村 豊太郎, 後藤 和茂, 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL, 情報処理学会研究報告. 計算機アーキテクチャ研究会報告, Vol.2011, No.21, pp.1-10, 2011.11, 様々な分野においてネットワーク解析に対する期待は高まりを見せているものの,非常に大規模なネットワークを扱うための計算量が課題とされている.そこで我々は,一般的な計算機環境上での最短路問題と中心性指標に対する,計算機のメモリ階層構造を考慮した高速計算手法を提案し,NETAL (NETwork Analysis Library) として実装した.NETAL は NUMA アーキテクチャを考慮して,計算機資源要求の衝突を回避する affinity 設定を行なっている.実ネットワークに対する数値実験に用いて,先行研究と比べ最も高速であることを示した.前処理を必要としない NETAL は,道路ネットワーク USA-road-d.USA.gr に対する全対全最短路長計算を 7.75 日で計算することに成功した.これは Δ-stepping algorithm の 432.4 倍,9th DIMACS 参照実装の 228.9 倍の性能に相当する.さらに,GraphCT を用いて 21 日間必要とする USA-road-d.LKS.gr に対する betweenness 計算は,我々の実装では複数の中心性指標 closeness,graph,stress,betweenness を同時に計算し 1 日で終了する.SSCA#2 を用いた R-MAT グラフに対する betweenness 計算に対しても我々の実装は 2.4-3.7 倍の性能を示している.. |
| 104. | 藤澤 克樹, 安井 雄一郎, 高宮 安仁, 佐藤 仁, 最適化分野におけるクラウド技術の利用, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, Vol.56, No.6, pp.318-324, 2011.06, 最適化問題に対するクラウド・コンピューティングの適用には様々な方法が提案されている.例えば大規模最適化問題に対して数値実験等を行うために,必要なときに,必要な量だけ計算機資源をインターネット上から調進してくるIaaSと呼ばれる技術の利用等がある.本解説ではこの利用方法に関連するクラウド技術による計算資源の動的な確保について触れてから,最適化問題として大規模なネットワークデータにおけるグラフ探索と応用,およびクラウド・コンピューティングの技術を用いた高速化などに関する話題について説明していく.. |
| 105. | 安井 雄一郎, 藤澤 克樹, 鳥海 重喜, 田口 東, 大規模最短路問題に対するダイクストラ法の高速化 (最適化モデルとアルゴリズムの新展開--RIMS研究集会報告集), 数理解析研究所講究録, Vol.1726, No.1726, pp.62-72, 2011.02. |
| 106. | Yuichiro Yasui, Katsuki Fujisawa, Kazushige Goto, Naoyuki Kamiyama, Mizuyo Talcamatsu, Netal: High-performance implementation of network analysis library considering computer memory hierarchy, Journal of the Operations Research Society of Japan, 10.15807/jorsj.54.259, Vol.54, No.4, pp.259-280, 2011.12, 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.. |
| 107. | Katsuki Fujisawa, Jun Ya Gotoh, A special issue of the scope (seminar on computation and optimization for new extensions), Journal of the Operations Research Society of Japan, Vol.54, No.4, p.141, 2011.12. |
| 108. | 藤澤 克樹, 2-A-6 最適化と計算に関する最新の傾向について(計算と最適化の新展開), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2011, pp.124-125, 2011.03. |
| 109. | 藤澤 克樹, 遠藤 敏夫, 大規模半正定値計画問題に対する内点法アルゴリズムの高速計算, Tsubame ESJ. : e-science journal, Vol.7, pp.2-6, 2012.12. |
| 110. | James S. M. Anderson, Maho Nakata, Ryo Igarashi, Katsuki Fujisawa, Makoto Yamashita, The second-order reduced density matrix method and the two-dimensional Hubbard model, 10.1016/j.comptc.2012.08.018, 2012.07, 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 $P$, $Q$, $G$, $T1$ and $T2^prime$ conditions in the two-dimension al Hubbard model case and we conduct a thorough study applying the $4 imes 4$ Hubbard model employing a coefficients. Within the Hubbard Hamilt onian we found that even in the intermediate setting, where $U/t$ is between 4 and 10, the $P$, $Q$, $G$, $T1$ and $T2^prime$ conditions re produced good ground state energies.. |
| 111. | 渡部 優, 藤澤 克樹, 鈴村 豊太郎, PGAS言語X10による半正定値計画問題の実装と評価, 研究報告ハイパフォーマンスコンピューティング（HPC）, Vol.2012, No.33, pp.1-8, 2012.03, 近年では 1 つの CPU に複数のコアを載せた，マルチコア・メニーコアといったものが主流となってきている．また，GPU を汎用演算処理に用いたヘテロ型アーキテクチャや，それらを組み合わせた大規模クラスタなど，プログラミングにおける計算機の環境が大きく変化している．そのような環境の中で，計算機資源を活かしたアプリケーション開発を行うには，高生産・高性能なプログラミング言語が不可欠となる．そこで本研究では，並列分散プログラミング言語の 1 つである PGAS 言語 X10 に焦点を当て，並列アプリケーションとして半正定値計画問題を実装・評価を行う．そして，その実装・評価を通して，X10 の並列分散プログラミング言語としての有用性・問題点を明らかにすることを目的とする．本研究の実験では，X10 による並列実装でのノード内マルチスレッド実行により，約 2.5 倍の性能向上を確認した．In recent years, multi-core or many-core CPU has become mainstream. As the advent of heterogeneous architecture with a general-purpose processing GPU or large-scale clusters, an environment of computer programming has changed greatly. In such an environment, the high productivity and the high performance programming language is essential in order to develop applications that take advantage of computational resources. In this study, we focused on the X10 PGAS language which has been developed by IBM Research aiming at a balance of high productivity and high performance. And we implemented and evaluated SemiDefinite Programming on X10. Through its implementation and evaluation, and we aim to clarify the usefulness and problems of parallel and distributed as a programming language of X10. As the result of experiment, the performance has improved 2.5 times compared to single thread of execution by a multi-threaded within a node.. |
| 112. | 渡部優, 藤澤克樹, 鈴村豊太郎, PGAS言語X10による半正定値計画法の実装と評価, 先進的計算基盤システムシンポジウム論文集, Vol.2012, No.2012, pp.61-62, 2012.05. |
| 113. | 藤澤 克樹, 最適化と計算の今後 : 大規模問題をどこまで解決できるのか?(特別講演(1)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2013, pp.2-3, 2013.09. |
| 114. | 藤澤 克樹, 遠藤 敏夫, 大規模半正定値計画問題に対する内点法アルゴリズムの高速計算, 計算工学講演会論文集 Proceedings of the Conference on Computational Engineering and Science, Vol.18, p.4p, 2013.06. |
| 115. | 岩渕圭太, 佐藤仁, 安井雄一郎, 藤澤克樹, 松岡聡, 不揮発性メモリを用いたGraph500ベンチマークの大規模実行へ向けた予備評価, 研究報告ハイパフォーマンスコンピューティング（HPC）, Vol.2013, No.31, pp.1-6, 2013.02, 近年大規模グラフはさまざまな分野で出現しており，DRAM の容量を増設することによる消費電力増加の問題やそもそもシングルノード上の DRAM 容量を超えるグラフも出現している．本研究ではGraph 500 ベンチマークに対して不揮発性メモリを補助的に利用することで性能低下を最小限に押さえながらシングルノード上でできる限り大容量のグラフを扱えるようにすることを目指している．そこでまず本論文ではDRAM に乗りきらない問題サイズを実行するための手法を提案し，DRAM と不揮発性メモリの容量の比率が実行性能にどのような影響を与えるかについての予備評価を行った．. |
| 116. | 岩渕圭太, 佐藤仁, 安井雄一郎, 藤澤克樹, 松岡聡, 不揮発性メモリを用いたGraph500ベンチマークの大規模実行へ向けた予備評価, 先進的計算基盤システムシンポジウム論文集, Vol.2013, No.2013, pp.130-131, 2013.05. |
| 117. | 岩渕圭太, 佐藤仁, 安井雄一郎, 藤澤克樹, 松岡聡, 不揮発性メモリを用いたHybrid-BFSアルゴリズムの最適化と性能解析, 情報処理学会研究報告. [ハイパフォーマンスコンピューティング], Vol.2013, No.3, pp.1-9, 2013.09, 近年さまざまな分野で大規模なグラフに対する高速な処理が求められているが,その処理の特性上,妥当な性能を得るためには全てのデータを DRAM 上にロードして実行する必要があり,その結果,DRAM の容量を増設することによる消費電力,価格面でのコストの増加が問題となっている.そこで,Hybrid-BFS アルゴリズムに対して不揮発性メモリを補助的に利用した場合の I/O の最適化,性能低下要因の解析を行うことで性能低下を抑えながら大規模グラフ処理が実行可能かの評価を行った.その結果,一部データを不揮発性メモリに退避することで DRAM 用量が半分の環境において性能低下を 47.1% まで抑えることができた.また,参照され難いエッジデータをさらに退避することで性能の低下を抑えながらより DRAM 使用量が削減可能なことの確認,さらに,性能低下要因の特定とその改善案を示し,性能低下を抑えながら大規模グラフ処理の実現可能性が示唆された.. |
| 118. | 安井 雄一郎, 藤澤 克樹, 竹内 聖悟, 湊 真一, ULIBCライブラリを用いた共有メモリ型並列アルゴリズムの高速化, ハイパフォーマンスコンピューティングと計算科学シンポジウム論文集, Vol.2014, No.2014, pp.106-115, 2013.12. |
| 119. | Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Maho Nakata, Parallel Computing for Large-scale Semidefinite Programs, Tokyo Institute of Technology Bulletin, 2013.02. |
| 120. | 成澤 龍人, 安井 雄一郎, 藤澤 克樹, 小林 和博, 2-F-10 最速フローを用いた避難所の評価(最適化(2)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2013, pp.262-263, 2013.09. |
| 121. | 安井 雄一郎, 藤澤 克樹, 後藤 和茂, 1-E-4 大規模グラフに対する幅優先探索の高速化(探索理論), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2013, pp.86-87, 2013.09. |
| 122. | 藤澤克樹, 超大規模半正定値計画問題に対する高性能汎用ソルバの開発と評価, 情報処理学会研究報告. AL, アルゴリズム研究会報告, Vol.2014, No.9, pp.1-2, 2014.02. |
| 123. | 安井 雄一郎, 藤澤 克樹, 計算機のメモリ階層構造を考慮した実装手法 (特集 実装における計算技術 : アルゴリズムと数理の現実場面での活躍), オペレーションズ・リサーチ, Vol.59, No.10, pp.601-607, 2014.10, 近年の計算機技術の発展や,数理科学分野におけるアルゴリズムの進歩により,以前では考えられない規模の問題を扱うことができるようになってきた.その一方で,実装したソフトウェアが期待される性能を示さないといった場面も少なくない.本稿ではなぜそのような状況になってしまうのか,現在主流となるNUMAアーキテクチャを有したプロセッサの特性を示し,高速に動作することが求められるアルゴリズム実装の際にどのような点を考慮しながら進めれば良いか,それらの改善方法について解説を行う.. |
| 124. | 藤澤 克樹, 次世代スーパコンピュータ技術を用いた超大規模グラフ解析と実社会への応用 (特集 データを読み解く技術 : ビッグデータ,e-サイエンス,潜在的ダイナミクス) -- (e-サイエンス時代のアルゴリズム研究), 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, Vol.97, No.5, pp.374-378, 2014.05, 新しいスーパコンピュータ(スパコン)の応用として大規模なグラフ解析やデータ処理が注目を集めている.グラフ解析の応用分野としては大規模災害等での避難誘導計画,社会公共政策や企業経営等のためソーシャルネットワーク等の大規模データの有効活用等が想定されているが,計算量やデータ量更に電力使用量などの規模が非常に大きく,従来の手法では処理が困難である.そのためハイパフォーマンスコンピューティング分野の技術を用いて大規模なグラフ解析を行う研究が盛んに行われており,その中からGraph500ベンチマークとグラフ解析の性能について解説を行う.更に本稿では次世代のポストペタスケールスパコンにおける最重要カーネルの一つである超大規模グラフ処理を実現するための研究プロジェクトを紹介する.具体的には大規模グラフデータに対するリアルタイムストリーミング処理,計算量とデータ移動量更に省電力性を考慮したグラフ最適化アルゴリズム,ストレージの階層性を考慮した大規模グラフデータストアなどの研究を現在推進している.. |
| 125. | 藤澤 克樹, 品野 勇治, 最適化と計算の今後 : 大規模問題をどこまで解決できるのか? (特集 研究の楽しさ), オペレーションズ・リサーチ, Vol.59, No.1, pp.11-19, 2014.01, 近年,大規模かつ複雑な最適化問題を高速に解く需要はさまざまな産業界や学術分野において急速に高まりつつある.これからの研究においては最先端理論(Theory)+超大規模実データ(Practice)+最新計算技術(Computation)の三つを有機的に組み合わせることによって,実用に耐えうる解決策の提示と大規模最適化問題を扱う際の先例となることが求められている.本稿では最適化と計算に関する最新の傾向に触れるとともに,最適化の計算の今後についても考えていきたい.. |
| 126. | 岩渕圭太, 佐藤仁, 溝手竜, 安井雄一郎, 藤澤克樹, 松岡聡, 不揮発性メモリを用いたHybrid BFSアルゴリズム, 情報処理学会研究報告. AL, アルゴリズム研究会報告, Vol.2014, No.7, p.1, 2014.02, 近年、SNS 解析、道路ネットワークの経路探索、スマートグリッド、創薬、遺伝子解析等の様々な分野で大規模なグラフに対する高速処理が求められているが、従来手法では、妥当な性能を得るためには全てのデータを DRAM 上にロードして実行する必要があり、その結果、DRAM の容量を増設することによる消費電力、価格の面でのコストの増加が問題になっている。そこで、我々は、BFS に対して NVM(不揮発性メモリ) を補助的に利用することで、DRAM の容量を超えるサイズのグラフを性能低下を抑えながら高速に処理する手法を提案し、開発を進めている。現時点で、省電力なビッグデータ処理のランキングである GreenGraph500 (2013 年 11 月) のビッグデータカテゴリのリストで 4 位 (1 ノードでは世界一) を達成した。. |
| 127. | 安井雄一郎, 藤澤克樹, NUMAを考慮した並列幅優先探索, 情報処理学会研究報告. AL, アルゴリズム研究会報告, Vol.2014, No.8, p.1, 2014.02, 本発表では,NUMA アーキテクチャを有する計算機上で高い性能を示す幅優先探索について説明する.提案手法は汎用的なグラフ分割手法を用いて,プロセッサソケットと対となるローカルメモリを考慮し,局所性を高めることに成功している.本研究で開発した実装は,HPC 分野において注目されている幅優先探索の性能を用いたベンチマーク Graph500 の 1 ノード最高性能を,幅優先探索の省電力性能を用いたベンチマーク Green Graph500 では世界 1 位をそれぞれ獲得している.. |
| 128. | 田中 勇真, 池上 敦子, 松井 泰子, 藤澤 克樹, 安井 雄一郎, 2-H-5 プリミティブ・ソーティング・ネットワークの高速数え上げ算法(最適化(2)), 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2014, pp.276-277, 2014.08. |
| 129. | 成澤 龍人, 安井 雄一郎, 藤澤 克樹, 小林 和博, 2-E-1 緊急避難計画に対する普遍的最速流の実験的解析(防災・減災), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2014, pp.220-221, 2014.03. |
| 130. | 安井 雄一郎, 藤澤 克樹, 1-F-4 省電力性能を考慮した幅優先探索(大規模計算), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2014, pp.102-103, 2014.03. |
| 131. | 藤澤 克樹, 松尾 久人, 安井 雄一郎, 招待講演 グラフ解析と最適化技術で実現する都市OS, システム制御情報学会研究発表講演会講演論文集, Vol.59, p.4p, 2015.05. |
| 132. | Keita Iwabuchi, Hitoshi Sato, Yuichiro Yasui, Katsuki Fujisawa, Satoshi Matsuoka, NVM-based Hybrid BFS with memory efficient data structure, Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014, 10.1109/BigData.2014.7004270, pp.529-538, 2015.01, © 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 % 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.. |
| 133. | 藤澤 克樹, 安井 雄一郎, 松尾 久人, 2-B-1 グラフ解析と最適化技術で実現する都市OS(統一テーマ関連(1)), 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2015, pp.208-209, 2015.03. |
| 134. | 藤澤 克樹, 大規模グラフ解析と都市OSの開発 : ヒト・モノのモビリティに関する新しい数理モデルとその応用, 回路とシステムワークショップ論文集 Workshop on Circuits and Systems, Vol.29, pp.130-135, 2016.05. |
| 135. | 藤澤 克樹, スパースモデリングのための高速・省電力計算 (特集 スパースモデリングの発展 : 原理から応用まで) -- (情報通信工学分野への応用), 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, Vol.99, No.5, pp.444-449, 2016.05. |
| 136. | 藤澤 克樹, スパースモデリングのための高速・省電力計算 (特集 スパースモデリングの発展 : 原理から応用まで) -- (情報通信工学分野への応用), 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, Vol.99, No.5, pp.444-449, 2016.05. |
| 137. | 今村智史, 安井雄一郎, 稲富雄一, 藤澤克樹, 井上弘士, 小野貴継, コードレベル性能最適化が電力効率に与える影響の分析, 情報処理学会研究報告(Web), Vol.2016, No.HPC-155, p.Vol.2016‐HPC‐155,No.21,1‐8 (WEB ONLY), 2016.08. |
| 138. | 垣深悠太, 安井雄一郎, 小野貴継, 稲富雄一, 藤澤克樹, 井上弘士, CPUとDRAMへの電力バジェット配分を考慮したGraph500の性能評価, 情報処理学会研究報告(Web), Vol.2016, No.HPC-155, p.Vol.2016‐HPC‐155,No.16,1‐6 (WEB ONLY), 2016.08. |
| 139. | 秦希望, 藤澤克樹, 藤澤克樹, 松林達史, 避難計画モデルに対する辞書式最速流の幾何学的分解と解析, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2017, p.165‐166, 2017.03. |
| 140. | 田中智, 秦希望, 金子有旗, 藤澤克樹, 藤澤克樹, 辞書式最速流と深層学習を用いた避難完了時間の予測, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, Vol.2017, p.163‐164, 2017.03. |
| 141. | 藤澤克樹, ヒト・モノのモビリティの数理モデルと産業応用, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, Vol.2017, p.174‐175, 2017.09. |
| 142. | Satoshi Imamura, Yuichiro Yasui, Koji Inoue, Takatsugu Ono, Hiroshi Sasaki, Katsuki Fujisawa, Power-Efficient Breadth-First Search with DRAM Row Buffer Locality-Aware Address Mapping, Proceedings of HPGDMP 2016: High Performance Graph Data Management and Processing - Held in conjunction with SC 2016: The International Conference for High Performance Computing, Networking, Storage and Analysis, 10.1109/HPGDMP.2016.010, pp.17-24, 2017.01, © 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% 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.. |
| 143. | 藤澤克樹, 大規模グラフ解析と都市OSの開発~ヒト・モノのモビリティに関する新しい数理モデルとその応用~, 電子情報通信学会技術研究報告, Vol.118, No.33(SIP2018 1-20), p.1, 2018.05. |
| 144. | 藤澤 克樹, 秦 希望, データサイエンスと最適化 : ヒト・モノのモビリティの数理モデル (特集 データサイエンスの数理 : 数理で読み解くデータの価値), 数理科学, Vol.57, No.6, pp.37-43, 2019.06. |
| 145. | 藤澤 克樹, サイバーフィジカルシステムにおけるモビリティ最適化エンジンの開発 (特集 B2Bソリューション), パナソニック技報 = Panasonic technical journal, Vol.65, No.1, pp.4-8, 2019.05. |
| 146. | 立岩 斉明, 品野 勇治, 吉田 明広, 鍛冶 静雄, 安田 雅哉, 藤澤 克樹, 最短格子ベクトル問 題求解における Ubiquity Generator Framework を用いた大規模 MPI 並列化, 研究報告 ハイパフォーマンスコンピューティング(HPC), Vol.2020-HPC-176, No.1, pp.1-10, 2020.08. |
| 147. | 藤澤 克樹, 巨大行列とグラフ解析 (特集 巨大行列), 数学セミナー, Vol.59, No.2, pp.24-28, 2020.02. |
| 148. | 藤澤克樹, 大規模グラフ解析の高速計算と実社会への応用, 電子情報通信学会誌, Vol.1164, pp.360-366, 2021.04. |
| 149. | Jun Ya Gotoh, Katsuki Fujisawa, Convex optimization approaches to maximally predictable portfolio selection, Optimization, 10.1080/02331934.2012.741237, 2014.11, [URL], 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.. |
| 150. | Katsuki Fujisawa, Large-scale graph analysis and its applications using techniques of the next generation super computer, Journal of the Institute of Electronics, Information and Communication Engineers, 2014. |
| 151. | James S.M. Anderson, Maho Nakata, Ryo Igarashi, Katsuki Fujisawa, Makoto Yamashita, The second-order reduced density matrix method and the two-dimensional Hubbard model, Computational and Theoretical Chemistry, 10.1016/j.comptc.2012.08.018, 2013.01, [URL], 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.. |
| 152. | Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Maho Nakata, Algorithm 925 Parallel solver for semidefinite programming problem having sparse schur complement matrix, ACM Transactions on Mathematical Software, 10.1145/2382585.2382591, 2012.11, [URL], 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.. |
| 153. | Katsuki Fujisawa, Jun Ya Gotoh, A special issue of the scope (seminar on computation and optimization for new extensions), Journal of the Operations Research Society of Japan, 2011.12. |
| 154. | Yuichiro Yasui, Katsuki Fujisawa, Kazushige Goto, Naoyuki Kamiyama, Mizuyo Talcamatsu, Netal High-performance implementation of network analysis library considering computer memory hierarchy, Journal of the Operations Research Society of Japan, 10.15807/jorsj.54.259, 2011.12, [URL], 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.. |
| 155. | Xiaoqing Bai, Hua Wei, Katsuki Fujisawa, Yong Wang, Semidefinite programming for optimal power flow problems, International Journal of Electrical Power and Energy Systems, 10.1016/j.ijepes.2007.12.003, 2008.07, [URL], 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.. |
| 156. | Xiao Qing Bai, Hua Wei, Katsuki Fujisawa, Solution of optimal power flow problems by semi-definite programming, Zhongguo Dianji Gongcheng Xuebao/Proceedings of the Chinese Society of Electrical Engineering, 2008.07, 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.. |
| 157. | Maho Nakata, Bastiaan J. Braams, Katsuki Fujisawa, Mituhiro Fukuda, Jerome K. Percus, Makoto Yamashita, Zhengji Zhao, Variational calculation of second-order reduced density matrices by strong N -representability conditions and an accurate semidefinite programming solver, Journal of Chemical Physics, 10.1063/1.2911696, 2008.05, [URL], 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.. |
| 158. | Katsuki Fujisawa, Kazuhide Nakata, Makoto Yamashita, Mituhiro Fukuda, SDPA Project Solving large-scale semidefinite programs, Journal of the Operations Research Society of Japan, 10.15807/jorsj.50.278, 2007.12, [URL], 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.. |
| 159. | T. Gunji, S. Kim, K. Fujisawa, M. Kojima, PHoMpara - Parallel implementation of the polyhedral homotopy continuation method for polynomial systems, Computing (Vienna/New York), 10.1007/s00607-006-0166-2, 2006.06, [URL], 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.. |
| 160. | Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Preprocessing sparse semidefinite programs via matrix completion, Optimization Methods and Software, 10.1080/10556780512331319523, 2006.02, [URL], 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.. |
| 161. | Kazuhide Nakata, Makoto Yamashita, Katsuki Fujisawa, Masakazu Kojima, A parallel primal-dual interior-point method for semidefinite programs using positive definite matrix completion, Parallel Computing, 10.1016/j.parco.2005.07.002, 2006.01, [URL], 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.. |
| 162. | Takayuki Gunji, Sunyoung Kim, Masakazu Kojima, Akiko Takeda, Katsuki Fujisawa, Tomohiko Mizutani, PHoM - A polyhedral homotopy continuation method for polynomial systems, Computing (Vienna/New York), 10.1007/s00607-003-0032-4, 2004.01, [URL], 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.. |
| 163. | Katsuki Fujisawa, Masakazu Kojima, Akiko Takeda, Makoto Yamashita, Solving large scale optimization problems via grid and cluster computing, Journal of the Operations Research Society of Japan, 10.15807/jorsj.47.265, 2004.01, [URL], 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.. |
| 164. | Makoto Yamashita, Katsuki Fujisawa, Masakazu Kojima, Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0), Optimization Methods and Software, 10.1080/1055678031000118482, 2003.08, [URL], 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.. |
| 165. | M. Yamashita, Katsuki Fujisawa, M. Kojima, SDPARA Semidefinite programming algorithm paRAllel version, Parallel Computing, 10.1016/S0167-8191(03)00087-5, 2003.08, [URL], 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.. |
| 166. | Kazuhide Nakata, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, Exploiting sparsity in semidefinite programming via matrix completion II Implementation and numerical results, Mathematical Programming, Series B, 10.1007/s10107-002-0351-9, 2003.02, [URL], 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.. |
| 167. | Akiko Takeda, Masakazu Kojima, Katsuki Fujisawa, Enumeration of all solutions of a combinatorial linear inequality system arising from the polyhedral homotopy continuation method, Journal of the Operations Research Society of Japan, 10.15807/jorsj.45.64, 2002.01, [URL], 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.. |
| 168. | Maho Nakata, Hiroshi Nakatsuji, Masahiro Ehara, Mitsuhiro Fukuda, Kazuhide Nakata, Katsuki Fujisawa, Variational calculations of fermion second-order reduced density matrices be semidefinite programming algorithm, Journal of Chemical Physics, 10.1063/1.1360199, 2001.05, [URL], 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.. |
| 169. | M. Ohsaki, K. Fujisawa, N. Katoh, Y. Kanno, Semi-definite programming for topology optimization of trusses under multiple eigenvalue constraints, Computer Methods in Applied Mechanics and Engineering, 10.1016/S0045-7825(99)00056-0, 1999.11, [URL], 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.. |
| 170. | Mikio Kubo, Katsuki Fujisawa, The life span method - A new variant of local search, Japan Journal of Industrial and Applied Mathematics, 10.1007/BF03167318, 1998.01, [URL], 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.. |
| 171. | Katsuki Fujisawa, Masakazu Kojima, Kazuhide Nakata, Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Mathematical Programming, Series B, 10.1007/BF02614319, 1997.10, [URL], 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.. |
| 172. | 藤澤 克樹, 総説・論評・解説・書評・報告書リスト http://sdpa.imi.kyushu-u.ac.jp/~fujisawa/gyoseki2014.pdf . |
| 173. | 藤澤 克樹, 総説・論評・解説・書評・報告書リスト2015 http:⁄⁄sdpa.imi.kyushu-u.ac.jp⁄~fujisawa⁄gyoseki2015.pdf. |
本データベースの内容を無断転載することを禁止します。