The Use of Solvable Directed Graphs in a Jacobi-like Algorithm



Abstract Views
133

Downloads
152

Citations

Share

##plugins.themes.bootstrap3.article.sidebar##

Submitted Apr 20, 2021
Published Jul 14, 2021
10.24018/ejmath.2021.2.3.39

Abstract viewed = 133 times

Table of Contents

##plugins.themes.bootstrap3.article.main##

In this paper, we introduce a Jacobi-like algorithm (we call D-NJLA) to reduce a real nonsymmetric n × n matrix to a real upper triangular form by the help of solvable directed graphs. This method uses only real arithmetic and a sequence of orthogonal similarity transformations and achieves ultimate quadratic convergence. A theoretical analysis is constructed and some experimental results are given.

Keywords: eigenvalues and eigenvectors, Jacobi-like algorithms, transformation methods

References

  1. A. Jarden, V. E. Levit and R. Shwartz, “Matchings in graphs and groups,” Discrete Applied Mathematics, vol. 247, 2018, pp. 216–224.
     Google Scholar
  2. A.D. Timothy and H. Yifan, “The University of Florida Sparse Matrix Collection,” ACM Transactions on Mathematical Software 38, vol. 1, 25 pages, December 2011.
     Google Scholar
  3. A. R. Gourlay and G. A. Watson, Computational Methods for Matrix Eigenproblems, Chichester: John Wiley and Sons, 1973.
     Google Scholar
  4. C. Mehl, “On Asymptotic Convergence of Nonsymmetric Jacobi Algorithms,” SIAM Journal on Matrix Analysis and Applications, vol. 30, pp. 291–311, 2008.
     Google Scholar
  5. C. G. J. Jacobi, “Uber ein leichtes Verfahren die in der Theorie der Sakular storungen vorkommenden gleichungen numerisch aufzuloen,” Reine Agnew. Math., vol. 30, 1846, pp. 51–95.
     Google Scholar
  6. C. P. Huang, “A Jacobi-type method for triangularizing an arbitrary matrix,” SIAM J. Num. Anal., vol. 12, 1975, pp. 566–670.
     Google Scholar
  7. F. M. Dopico, P. Koev and J. M. Molera, “Implicit standart Jacobi gives high relative accuracy,” Numerische Mathematik, vol. 113, 2009, pp. 519–553.
     Google Scholar
  8. G. H. Golub and H. A. Van Der Vorst, “Eigenvalue computation in the 20th century,” Journal of Computational and Applied Mathematics, vol. 123, 2000, pp. 35–65.
     Google Scholar
  9. G. H. Golub and C. F. Van Loan, Matrix Computations, Baltimore: The Johns Hopkins University Press, 2013.
     Google Scholar
  10. G. W. Stewart, “A Jacobi-like algorithm for computing the Schur decomposition of a non-Hermitian matrix,” SIAM J. Sci. Statist. Comput., vol. 6, 1985, pp. 853-864.
     Google Scholar
  11. G. W. Stewart and J. Sun, Matrix perturbation theory, Boston: Academic Press, Inc., 1990.
     Google Scholar
  12. H. Rutishauser, “The Jacobi Method for Real Symmetric Matrices,” Applied Soft Computing, vol. 9, 1966, pp. 1-10.
     Google Scholar
  13. J. Greenstadt, “A method for finding roots of arbitrary matrices,” Math. Tables Aids Comput., vol. 9, 1955, pp. 47–52.
     Google Scholar
  14. J. H. Wilkinson, “Note on the quadratic convergence of the cyclic Jacobi process,” Numerische Mathematik, vol. 4, 1962, pp. 296–300.
     Google Scholar
  15. L. A. Pipes and L. R. Harvill, Applied Mathematics for Engineers and Physicists, Dover Publications, Inc., Mineola, New York, 2014.
     Google Scholar
  16. L. Mirsky, An Introduction to Linear Algebra, Oxford: Clarendon Press, 1955.
     Google Scholar
  17. M. Bezem, C. Grabmayer and M. Walicki, “Expressive power of digraph solvability,” Annals of Pure and Applied Logic, vol. 163, 2012, pp. 200– 213.
     Google Scholar
  18. M. Lotkin, “Characteristic values of arbitrary matrices,” Quart. Apply. Math., vol. 14, 1956, pp. 267-275.
     Google Scholar
  19. N. Deo, Graph Theory with Applications to Engineering and Computer Sciences, Prentice Hall, 1974.
     Google Scholar
  20. P. Eberlein, “On the Schur Decomposition of a Matrix for Parallel Computation,” IEEE Transaction on Computers, vol. 36, 1987, pp. 167– 174.
     Google Scholar
  21. R. Causey, “Computing eigenvalues of non-Hermitian matrices by methods of Jacobi type,” J. Soc. Indust. Applied Math., vol. 6, 1958, pp. 172-181.
     Google Scholar
  22. S. Dyrkolbotn and M. Walicki, “Kernels in digraphs that are not kernel perfect,” Discrete Mathematics, vol. 312, 2012, pp. 2498-2505.
     Google Scholar
  23. V. Hari and E. Begovic, “On the global convergence of the Jacobi ´ method,” PAMM. Proc. Appl. Math. Mech., vol. 16, 2016, pp. 725-726.
     Google Scholar
  24. W. F. Mascarenhas, “On the Convergence of the Jacobi method for Arbitrary Orderings,” SIAM J. Matrix Anal. Appl. vol. 16, 1995, pp. 1197-1209.
     Google Scholar
  25. W. Y. Mei, J. Ming, L. Shuai, Q. X. Lin and Q. W. Qiangand, “An Implementation of Matrix Eigenvalue Decomposition with Improved Jacobi Algorithm,” IEEE Computer Society: Proceedings of the 2010 First International Conference on Pervasive Computing, Signal Processing and Applications, 2010, pp. 952-955.
     Google Scholar
  26. Y. Saad, Numerical Methods for Large Eigenvalue Problems, Manchester University Press Series in Algorithms and Architectures for Advanced Scientific Computing, 1992.
     Google Scholar