×

Factorization of saddle-point matrices in dynamical systems optimization – reusing pivots. (English) Zbl 1410.65079

Summary: In this paper we consider the application of direct methods for solving a sequence of saddle-point systems. Our goal is to design a method that reuses information from one factorization and applies it to the next one. In more detail, when we compute the pivoted \(LDL^T\) factorization we speed up computation by reusing already computed pivots and permutations. We develop our method in the frame of dynamical systems optimization. Experiments show that the method improves efficiency over Bunch-Parlett and Bunch-Kaufman while delivering the same results.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Altman, A.; Gondzio, J., Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11, 1-4, 275-302 (1999) · Zbl 0957.90101
[2] Ascher, U.; Russell, R. D., Reformulation of boundary value problems into “standard” form, SIAM Rev., 23, 2, 238-254 (1981) · Zbl 0461.34021
[3] Ascher, U. M.; Petzold, L. R., Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations (1998), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 0908.65055
[4] Ashcraft, C.; Grimes, R. G.; Lewis, J. G., Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl., 20, 2, 513-561 (1998) · Zbl 0923.65010
[5] Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034
[6] Branicky, M. S.; Curtiss, M. M.; Levine, J.; Morgan, S., Sampling-based planning, control and verification of hybrid systems, IEE Proc., Control Theory Appl., 153, 575-590 (September 2006)
[7] Bunch, J. R.; Kaufman, L., Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 31, 137, 163-179 (1977) · Zbl 0355.65023
[8] Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655 (1971)
[9] Chan, S.; Phoon, K.; Lee, F., A modified Jacobi preconditioner for solving ill-conditioned Biot’s consolidation equations using symmetric quasi-minimal residual method, Int. J. Numer. Anal. Methods Geomech., 25, 10, 1001-1025 (2001) · Zbl 1065.74605
[10] Chutinan, A.; Krogh, B. H., Computational techniques for hybrid system verification, IEEE Trans. Automat. Control, 48, 1, 64-75 (2003) · Zbl 1364.93457
[11] Cuthill, E.; McKee, J., Reducing the bandwidth of sparse symmetric matrices, (Proceedings of the 1969 24th National Conference. Proceedings of the 1969 24th National Conference, ACM ’69 (1969), ACM: ACM New York, NY, USA), 157-172
[12] Duff, I. S., Ma57—a code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Software, 30, 2, 118-144 (2004) · Zbl 1070.65525
[13] Duff, I. S.; Pralet, S., Strategies for scaling and pivoting for sparse symmetric indefinite problems, SIAM J. Matrix Anal. Appl., 27, 2, 313-340 (2005) · Zbl 1092.65037
[14] Duff, I. S.; Reid, J. K., The multifrontal solution of indefinite sparse symmetric linear systems, ACM Trans. Math. Software, 9, 3, 302-325 (Sept. 1983)
[15] Gibbs, N. E.; Poole, W. G.; Stockmeyer, P. K., An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM J. Numer. Anal., 13, 2, 236-250 (1976) · Zbl 0329.65024
[16] Golub, G. H.; Van Loan, C. F., Matrix Computations, Johns Hopkins Stud. Math. Sci. (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[17] Gondzio, J.; Grothey, A., Direct solution of linear systems of size \(10^9\) arising in optimization with interior point methods, (Parallel Processing and Applied Mathematics (2006), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 513-525 · Zbl 1182.65050
[18] Greif, C.; Schötzau, D., Preconditioners for the discretized time-harmonic Maxwell equations in mixed form, Numer. Linear Algebra Appl., 14, 4, 281-297 (2007) · Zbl 1199.78010
[19] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1011.65010
[20] Hiptmair, R., Finite elements in computational electromagnetism, Acta Numer., 11, 237-339 (2002) · Zbl 1123.78320
[21] Kuřátko, J.; Ratschan, S., Combined global and local search for the falsification of hybrid systems, (Legay, A.; Bozga, M., Formal Modeling and Analysis of Timed Systems. Formal Modeling and Analysis of Timed Systems, Lecture Notes in Comput. Sci., vol. 8711 (2014), Springer International Publishing), 146-160 · Zbl 1448.68303
[22] Kuřátko, J.; Ratschan, S., Solving reachability problems by a scalable constrained optimization method (2017), submitted for publication, available at
[23] Lamiraux, F.; Ferré, E.; Vallée, E., Kinodynamic motion planning: connecting exploration trees using trajectory optimization methods, (2004 IEEE International Conference on Robotics and Automation, 2004, Proceedings, ICRA ’04, vol. 4 (2004)), 3987-3992
[24] Liu, W.-H.; Sherman, A. H., Comparative analysis of the Cuthill-Mckee and the reverse Cuthill-Mckee ordering algorithms for sparse matrices, SIAM J. Numer. Anal., 13, 2, 198-213 (1976) · Zbl 0331.65022
[25] Luksan, L., An implementation of recursive quadratic programming variable metric methods for linearly constrained nonlinear minimax approximation, Kybernetika, 21, 1, 22-40 (1985) · Zbl 0548.90061
[26] Lukšan, L.; Tůma, M.; Hartman, J.; Vlček, J.; Ramešová, N.; Šiška, M.; Matonoha, C., UFO 2014—Interactive System for Universal Functional Optimization (2014), Institute of Computer Science of the Academy of Sciences of the Czech Republic, Technical report V-1218
[27] Lukšan, L.; Matonoha, C.; Vlček, J., Interior-point method for non-linear non-convex optimization, Numer. Linear Algebra Appl., 11, 5-6, 431-453 (2004) · Zbl 1164.90422
[28] Lukšan, L.; Vlček, J., Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems, Numer. Linear Algebra Appl., 5, 3, 219-247 (1998) · Zbl 0937.65066
[29] Lukšan, L.; Vlček, J., Numerical experience with iterative methods for equality constrained nonlinear programming problems, Optim. Methods Softw., 16, 1-4, 257-287 (2001), dedicated to Professor Laurence C.W. Dixon on the occasion of his 65th birthday · Zbl 1012.90064
[30] Möhlmann, E.; Theel, O., Stabhyli—a tool for automatic stability verification of non-linear hybrid systems, (HSCC’13—Hybrid Systems: Computation and Control (2013), ACM: ACM New York), 107-112 · Zbl 1362.93111
[31] Nocedal, J.; Wright, S. J., Numerical Optimization, Springer Ser. Oper. Res. Financ. Eng. (2006), Springer: Springer New York · Zbl 1104.65059
[32] Plaku, E.; Kavraki, L. E.; Vardi, M. Y., Hybrid systems: from verification to falsification by combining motion planning and discrete search, Form. Methods Syst. Des., 34, 2, 157-182 (2009) · Zbl 1192.68692
[33] Ruiz, D., A Scaling Algorithm to Equilibrate Both Rows and Columns Norms in Matrices (2001), Technical report, CM-P00040415
[34] Schenk, O.; Gärtner, K., Solving unsymmetric sparse systems of linear equations with PARDISO, Future Gener. Comput. Syst., 20, 3, 475-487 (2004)
[35] Scilab Enterprises, Scilab: Free and Open Source Software for Numerical Computation (2012), Scilab Enterprises: Scilab Enterprises Orsay, France
[36] Sorensen, D. C., Updating the Symmetric Indefinite Factorization with Applications in a Modified Newton’s Method (1977), Argonne National Lab.: Argonne National Lab. IL (USA), Technical report
[37] Tůma, M., A note on the \(L D L^T\) decomposition of matrices from saddle-point problems, SIAM J. Matrix Anal. Appl., 23, 4, 903-915 (2002) · Zbl 1050.65027
[38] Vavasis, S. A., Stable numerical algorithms for equilibrium systems, SIAM J. Matrix Anal. Appl., 15, 4, 1108-1131 (1994) · Zbl 0806.65020
[39] Vavasis, S. A., Stable finite elements for problems with wild coefficients, SIAM J. Numer. Anal., 33, 3, 890-916 (1996) · Zbl 0858.65112
[40] Wright, M. H., Interior methods for constrained optimization, Acta Numer., 1, 341-407 (1992) · Zbl 0766.65053
[41] Zutshi, A.; Sankaranarayanan, S.; Deshmukh, J. V.; Kapinski, J., A trajectory splicing approach to concretizing counterexamples for hybrid systems, (Decision and Control (CDC), 2013 IEEE 52nd Annual Conference (2013)), 3918-3925
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.