{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:36:24Z","timestamp":1763544984281,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T00:00:00Z","timestamp":1591833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T00:00:00Z","timestamp":1591833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["813211"],"award-info":[{"award-number":["813211"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Decomposition of large matrix inequalities for matrices with chordal sparsity graph has been recently used by Kojima et al. (Math Program 129(1):33\u201368, 2011) to reduce problem size of large scale semidefinite optimization (SDO) problems and thus increase efficiency of standard SDO software. A by-product of such a decomposition is the introduction of new dense small-size matrix variables. We will show that for arrow type matrices satisfying suitable assumptions, the additional matrix variables have rank one and can thus be replaced by vector variables of the same dimensions. This leads to significant improvement in efficiency of standard SDO software. We will apply this idea to the problem of topology optimization formulated as a large scale linear semidefinite optimization problem. Numerical examples will demonstrate tremendous speed-up in the solution of the decomposed problems, as compared to the original large scale problem. In our numerical example the decomposed problems exhibit linear growth in complexity, compared to the more than cubic growth in the original problem formulation. We will also give a connection of our approach to the standard theory of domain decomposition and show that the additional vector variables are outcomes of the corresponding discrete Steklov\u2013Poincar\u00e9 operators.<\/jats:p>","DOI":"10.1007\/s10107-020-01526-w","type":"journal-article","created":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T12:03:11Z","timestamp":1591876991000},"page":"105-134","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Decomposition of arrow type positive semidefinite matrices with application to topology optimization"],"prefix":"10.1007","volume":"190","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4414-0083","authenticated-orcid":false,"given":"Michal","family":"Ko\u010dvara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,11]]},"reference":[{"key":"1526_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(88)90240-6","volume":"107","author":"J Agler","year":"1988","unstructured":"Agler, J., Helton, W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear Algebra Appl. 107, 101\u2013149 (1988)","journal-title":"Linear Algebra Appl."},{"key":"1526_CR2","unstructured":"Fujisawa, K., Kim, S., Kojima, M., Okamoto, Y., Yamashita, M.: User\u2019s Manual for Sparsecolo: Conversion Methods for Sparse Conic-Form Linear Optimization. Tech. Rep, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo (2009)"},{"issue":"3","key":"1526_CR3","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"M Fukuda","year":"2001","unstructured":"Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion i: general framework. SIAM J. Optim. 11(3), 647\u2013674 (2001)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1526_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02612711","volume":"28","author":"A Griewank","year":"1984","unstructured":"Griewank, A., Toint, P.L.: On the existence of convex decompositions of partially separable functions. Math. Program. 28(1), 25\u201349 (1984)","journal-title":"Math. Program."},{"issue":"8","key":"1526_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"5","author":"R Grone","year":"1984","unstructured":"Grone, R., Johnson, C., S\u00e0, E., Wolkowitz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 5(8), 109\u2013124 (1984)","journal-title":"Linear Algebra Appl."},{"issue":"7","key":"1526_CR6","doi-asserted-by":"publisher","first-page":"2709","DOI":"10.1137\/090774446","volume":"70","author":"J Haslinger","year":"2010","unstructured":"Haslinger, J., Ko\u010dvara, M., Leugering, G., Stingl, M.: Multidisciplinary free material optimization. SIAM J. Appl. Math. 70(7), 2709\u20132728 (2010)","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"1526_CR7","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.laa.2010.04.012","volume":"433","author":"N Kakimura","year":"2010","unstructured":"Kakimura, N.: A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices. Linear Algebra Appl. 433(4), 819\u2013823 (2010)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1526_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0402-6","volume":"129","author":"S Kim","year":"2011","unstructured":"Kim, S., Kojima, M., Mevissen, M., Yamashita, M.: Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Math. Program. 129(1), 33\u201368 (2011)","journal-title":"Math. Program."},{"key":"1526_CR9","unstructured":"MOSEK ApS: The MOSEK Optimization Toolbox for MATLAB Manual. Version 8.0 (2016)"},{"issue":"2","key":"1526_CR10","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"K Nakata","year":"2003","unstructured":"Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion ii: implementation and numerical results. Math. Program. 95(2), 303\u2013327 (2003)","journal-title":"Math. Program."},{"issue":"6","key":"1526_CR11","doi-asserted-by":"publisher","first-page":"1759","DOI":"10.1137\/S0036142996313968","volume":"36","author":"J Petersson","year":"1999","unstructured":"Petersson, J.: A finite element analysis of optimal variable thickness sheets. SIAM J. Numer. Anal. 36(6), 1759\u20131778 (1999)","journal-title":"SIAM J. Numer. Anal."},{"key":"1526_CR12","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-94-009-1908-2_14","volume-title":"Applied and Industrial Mathematics: Venice-1, 1989","author":"A Quarteroni","year":"1991","unstructured":"Quarteroni, A., Valli, A.: Theory and application of Steklov\u2013Poincar\u00e9 operators for boundary-value problems. In: Spigler, R. (ed.) Applied and Industrial Mathematics: Venice-1, 1989, pp. 179\u2013203. Springer Netherlands, Dordrecht (1991)"},{"issue":"4","key":"1526_CR13","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends Optim. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01526-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01526-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01526-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:39:54Z","timestamp":1633833594000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01526-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,11]]},"references-count":13,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1526"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01526-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,6,11]]},"assertion":[{"value":"23 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}