The Use of Solvable Directed Graphs in a Jacobi-like Algorithm
##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.
References
-
A. Jarden, V. E. Levit and R. Shwartz, “Matchings in graphs and groups,” Discrete Applied Mathematics, vol. 247, 2018, pp. 216–224.
Google Scholar
1
-
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
2
-
A. R. Gourlay and G. A. Watson, Computational Methods for Matrix Eigenproblems, Chichester: John Wiley and Sons, 1973.
Google Scholar
3
-
C. Mehl, “On Asymptotic Convergence of Nonsymmetric Jacobi Algorithms,” SIAM Journal on Matrix Analysis and Applications, vol. 30, pp. 291–311, 2008.
Google Scholar
4
-
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
5
-
C. P. Huang, “A Jacobi-type method for triangularizing an arbitrary matrix,” SIAM J. Num. Anal., vol. 12, 1975, pp. 566–670.
Google Scholar
6
-
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
7
-
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
8
-
G. H. Golub and C. F. Van Loan, Matrix Computations, Baltimore: The Johns Hopkins University Press, 2013.
Google Scholar
9
-
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
10
-
G. W. Stewart and J. Sun, Matrix perturbation theory, Boston: Academic Press, Inc., 1990.
Google Scholar
11
-
H. Rutishauser, “The Jacobi Method for Real Symmetric Matrices,” Applied Soft Computing, vol. 9, 1966, pp. 1-10.
Google Scholar
12
-
J. Greenstadt, “A method for finding roots of arbitrary matrices,” Math. Tables Aids Comput., vol. 9, 1955, pp. 47–52.
Google Scholar
13
-
J. H. Wilkinson, “Note on the quadratic convergence of the cyclic Jacobi process,” Numerische Mathematik, vol. 4, 1962, pp. 296–300.
Google Scholar
14
-
L. A. Pipes and L. R. Harvill, Applied Mathematics for Engineers and Physicists, Dover Publications, Inc., Mineola, New York, 2014.
Google Scholar
15
-
L. Mirsky, An Introduction to Linear Algebra, Oxford: Clarendon Press, 1955.
Google Scholar
16
-
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
17
-
M. Lotkin, “Characteristic values of arbitrary matrices,” Quart. Apply. Math., vol. 14, 1956, pp. 267-275.
Google Scholar
18
-
N. Deo, Graph Theory with Applications to Engineering and Computer Sciences, Prentice Hall, 1974.
Google Scholar
19
-
P. Eberlein, “On the Schur Decomposition of a Matrix for Parallel Computation,” IEEE Transaction on Computers, vol. 36, 1987, pp. 167– 174.
Google Scholar
20
-
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
21
-
S. Dyrkolbotn and M. Walicki, “Kernels in digraphs that are not kernel perfect,” Discrete Mathematics, vol. 312, 2012, pp. 2498-2505.
Google Scholar
22
-
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
23
-
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
24
-
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
25
-
Y. Saad, Numerical Methods for Large Eigenvalue Problems, Manchester University Press Series in Algorithms and Architectures for Advanced Scientific Computing, 1992.
Google Scholar
26