Competitive Algorithms for Large Scale Positive Definite Linear Systems of Equations Using an Error in Variables Optimization Model

Authors

  • Nezam Mahdavi-Amiri Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran. Author
  • Negin Bagherpour Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran. Author

DOI:

https://doi.org/10.17656/jzs.10821

Keywords:

Large scale problems, Dolan-More, ScaLAPACK

Abstract

We seek positive definite solutions of large scale overdetermined linear systems of equations with multiple right hand sides, where the coefficient and the right hand side matrices are respectively called data and target matrices. We recently proposed a new approach for solving such problems in small scales considering error in both the measured data and the target matrices and using a novel error formulation. We proposed four algorithms for solving small scale positive definite linear systems of equations with both full rank and rank deficient data matrices. Here, we extend our algorithms to solve large scale problems. The algorithms are implemented in Matlab and Fortran (using the ScaLAPACK library) respectively for small and large scale problems . ScaLAPACK is a parallel library written in Fortran to solve linear algebra problems such as computing matrix decompositions for large scale matrices. Block cyclic data distribution is used in ScaLAPACK to provide proper scalability, reliability, portability, flexibility and ease of use. Comparative numerical experiments with two available methods, the interior point method and a method based on quadratic programming, show that our approach produce a smaller standard deviation of the error entries and a smaller effective rank, as being desirable for control problems. Using the Dolan-More performance profiles we show that our proposed algorithms are more efficient and more accurate in computing proper solutions.

References

Alizadeh F., Pierre J., Heaberly A., Overton M. L. "Primal-dual interior point methods for semidefinite programming: convergence rates, stability and numerical result". SIAM J. Optim. Vol. 8, pp. 746-768. (1998). DOI: https://doi.org/10.1137/S1052623496304700

Aubry A., Maio A. D., Pallotta L., Farina A. "Maximum likelihood estimation of a structured covariance matrix with a condition number constraint". IEEE Trans. On Signal Processing. Vol. 60, No. 6, pp. 3004-3021. (2012). DOI: https://doi.org/10.1109/TSP.2012.2190408

Bagherpour N., Mahdavi-Amiri N. "A new error in variables model for solving positive definite linear system using orthogonal matrix decompositions". Numer. Alg. Vol. 72, No. 1, pp. 211-241. (2016). DOI: https://doi.org/10.1007/s11075-015-0042-2

Byrd R. H., Mary E., Nocedal J. "An Interior Point Algorithm for Large-Scale Nonlinear Programming". SIAM J. Optim. Vol. 9, No. 4, pp. 877-900. (1999). DOI: https://doi.org/10.1137/S1052623497325107

Cheng C. L., Kukush A., Mastronardi N., Paige C., Van Huffel S. "Total Least Squares and Errors-in-variables Modeling". Comput. Stat. Data An. Vol. 52, pp. 1076-1079. (2007). DOI: https://doi.org/10.1016/j.csda.2007.07.001

Deng Y., Boley D. "On the Optimal Approximation for the Symmetric Procrustes Problems of the Matrix Equation AXB = C". Proceedings of the International Conference on Computational and Mathematical Methods in Science and Engineering, Chicago. Pp. 159-168. (2007).

Dolan E. D, Moré J. J. "Benchmarking optimization software with performance profiles". Mathematical Programming. Vol. 91, pp. 201-213. (2012). DOI: https://doi.org/10.1007/s101070100263

Golub G. H., Van Loan C. F. "An analysis of the total least squares problem". SIAM J. Numer. Anal. Vol. 17, pp. 883-893. (1980). DOI: https://doi.org/10.1137/0717073

Hayami K., Yin J. F., Ito T. "GMRES method for least squares problems". SIAM. J. Matrix Anal. and Appl. Vol. 31, No. 5, pp. 2400-2430. (2010). DOI: https://doi.org/10.1137/070696313

Hnětynková I., Plešinger M., Sima D. M., Strakoš Z., Van Huffel S. "The total least squares problem in , A new classification with the relationship to the classical works". SIAM J. Matrix Anal. Appl. Vol. 32, No. 3, pp. 748-770. (2011). DOI: https://doi.org/10.1137/100813348

Hu H., Olkin I. "A numerical procedure for finding the positive definite matrix closest to a patterned matrix". Statistical and Probability Letters. Vol. 12, pp. 511-515. (1991). DOI: https://doi.org/10.1016/0167-7152(91)90006-D

Hu H. "Positive definite constrained least-squares estimation of matrices". Linear Algebra and its Applications. Vol. 229, pp. 167-174. (1995). DOI: https://doi.org/10.1016/0024-3795(94)00024-8

Van Huffel S., Vandewalle J. "Algebraic connections between the least squares and total least squares problems". Numer. Math. Vol. 55, pp. 431-449. (1989). DOI: https://doi.org/10.1007/BF01396047

Kang B., Jung S., Park P. "A new iterative method for solving total least squares problem". Proceeding of the 8th Asian Control Conference (ASCC), Kaohsiung, Taiwan, (2011).

Larson H. J. "Least squares estimation of the components of a symmetric matrix". Technometrics. Vol. 8, No. 2, pp. 360-362. (1966). DOI: https://doi.org/10.1080/00401706.1966.10490356

McInroy J., Hamann J. C. "Design and control of flexure jointed hexapods". IEEE Trans. Robotics and Automation. Vol. 16, No. 4, pp. 372-381. (2000). DOI: https://doi.org/10.1109/70.864229

Paige C. C., Strakoš Z. "Scaled total least squares fundamentals". Numer. Math. Vol. 91, pp. 117-146. (2000). DOI: https://doi.org/10.1007/s002110100314

Poignet P., Gautier M. "Comparison of Weighted Least Squares and Extended Kalman Filtering Methods for Dynamic Identification of Robots". Proceedings of the IEEE Conference on Robotics and Automation, San Francisco, CA, USA, pp. 3622-3627. (2000).

Woodgate K. G. "Least-squares solution of over positive semidefinite symmetric P". Linear Algebra Appl. Vol. 245, pp. 171-190. (1996). DOI: https://doi.org/10.1016/0024-3795(94)00238-X

Zhou L., Lin L., Wei Y., Qiao S. "Perturbation analysis and condition numbers of scaled total least squares problems". Numer. Algorithms. Vol. 51, pp. 381-399. (2009). DOI: https://doi.org/10.1007/s11075-009-9269-0

Banerjee S., Roy A. "Quadratic Forms, Linear Algebra and Matrix Analysis for Statistics". Chapman & Hall/CRC Texts in Statistical Sciences, pp. 441-442. (2014).

Carlen E. "Trace Inequalities and Quantum Entropy: An Introductory Course". Contemporary Mathematics, Vol. 529, AMS, pp. 73-140. (2009). DOI: https://doi.org/10.1090/conm/529/10428

Gill P. E. , Murray W., Wright M. H. "Numerical Linear Algebra and Optimization". Addison Wesley (1991).

Blackford L. S., Choi J., Cleary A., et. al. "Software, Environments and Tools: ScaLAPACK User's Guide", SIAM, Philadelphia. (1997). DOI: https://doi.org/10.1137/1.9780898719642

Higham N. J. "Functions of Matrices: Theory and Computation". SIAM, Philadelphia. (2008). DOI: https://doi.org/10.1137/1.9780898717778

Horn R. A., Johnson C. R. "Topics in Matrix Analysis". Cambridge University Press. (1991). DOI: https://doi.org/10.1017/CBO9780511840371

Van Huffel S., Vandewalle J. "The Total Least Squares Problem: Computational Aspects and Analysis". SIAM, Philadelphia. (1991). DOI: https://doi.org/10.1137/1.9781611971002

Krislock N. G. "Numerical Solution of Semidefinite Constrained Least Squares Problems". M. Sc. Thesis, University of British Colombia. (2003).

Demmel J. W. "Applied Numerical Linear Algebra". 3rd edition, SIAM, Philadelphia. (1996). DOI: https://doi.org/10.1137/1.9781611971446

Golub G. H., Van Loan C. F. "Matrix Computation". 4th edition, JHU Press. (2012).

Lancaster P., Rodman L. "Algebraic Riccati Equations". Clarendon Press. (1995). DOI: https://doi.org/10.1093/oso/9780198537953.001.0001

Magnus J. R., Neudecker H. "Matrix Differential Calculus with Applications in Statistics and Econometrics". 2nd edition, John Wiley & Sons. (1999).

Nocedal J., Wright S. J. "Numerical Optimization". Springer, New York. (1999). DOI: https://doi.org/10.1007/b98874

Higham N. J. "Computing the nearest correlation matrix (A problem from nance)". MIMS EPrint: 2006.70, http://eprints.ma.man.ac.uk/, (2006). Accessed 26 June (2012).

Petersen K. B., Pedersen M. S.: The Matrix Cookbook, http://orion.uwaterloo.ca/ hwolkowi/matrixcookbook.pdf, (2008). Accessed 11 January (2013).

Vershynin R.: Introduction to the non-asymptotic analysis of random matrices, http://arxiv.org/pdf/1011.3027v7.pdf, (2011). Accessed 01 February (2013).

American Mathematical Society, Eigenvalues and sums of Hermitian matrices, http://www.ams.org/bookstore/pspdf/gsm132prev.pdf, (2009). Accessed 18 March (2013).

Published

2020-12-20

How to Cite

Competitive Algorithms for Large Scale Positive Definite Linear Systems of Equations Using an Error in Variables Optimization Model. (2020). Journal of Zankoy Sulaimani - Part A, 22(2), 199-216. https://doi.org/10.17656/jzs.10821

Most read articles by the same author(s)

1 2 3 4 5 6 7 8 9 10 > >>