正定矩陣的特徵值分解問題在即時訊號處理系統中常扮演舉足輕重的角色，為了即時處理訊號源，我們必須在有限的時間內將特徵值與相對應
的特徵向量求出，循序演算法中這樣的計算複雜度需要O(n^4)時間，對
於即時系統來說，明顯地太過耗時，無法滿足系統的需求。在本論文中，
我們將提出一個以類神經網路為架構的平行計算模型，能有效並迅速地
將任意正定矩陣的所有特徵值與相對應於最大特徵值的一組特徵向量求
出，只需要O(n*(log n + m))的時間複雜度與O(n^3)個類神經元與連結
線即可完成所有的運算(n表示正定矩陣的大小為n*n；m表示系統收斂所
需的時脈次數)。

In the areas of real-time signal processing, it's important to
solve the eigenvalue decomposition problem of a positive defi-
nite matrix. For processing the signal in time, we must derive
the eigenvalues and eigenvectors in fixed units of time. This
problem can be solved by a sequential algorithm in O(n^4) time,
but this takes too long time for a real-time system to satisfy
the requirement. In this paper, we will propose a parallel sch-
eme that can solve all eigenvalues and the eigenvector corres-
ponding to the largest eigenvalue of a positive definite matrix
on the neural networks in O(n(log n + m)) time by using O(n^3)
neurons and O(n^3) links, where the size of the matrix is n*n
and the number of time clocks for the system to be convergent
is m.

[1] Z. Bai and J. Demmel, Design of parallel nonsymmetric
eigenroutine Toolbox, Part I, Research report 92-09,
university of Kentucky, Lexington, KY, (1992).
[2] A. N. Beavers, JR. and E. D. Denman, A computational method
for eigenvalues and eigenvectors of a matrix with real
eigenvalues, Numer. Math., 21 (1973), pp. 389-396.
[3] M. Berry and A. Sameh, Parallel algorithms for the singular
value and dense symmetric eigenvalue problem, J. Comput.
Appl. Math., 27 (1989), pp. 191-213.
[4] R. L. Burden and J. D. Faires, Numerical analysis,
Brooks/Cole Publishing Company, (1997).
[5] W. Chen and K. Hsieh, A neural sorting network with O(1)
time complexity, Information Processing Latters, 45 (1993),
pp. 309-313.
[6] T. H. Cormen, C. E. Leiserson and R. L. Rivest,
Introduction to algorithms, McGraw-Hill Book Company,
(1989).
[7] J. J. M. Cuppen, A divide and conquer method for the
symmetric tridiagonal eigenproblem, Number. Math., 36
(1981), pp. 1204-1245.
[8] E. D. Denman and A. N. Beavers, JR., The matrix sign
function and computations in systems, Appl. Math. Comput.,
2 (1976), pp. 63-94.
[9] E. D. Denman and J. Leyva-Ramos, Spectral decomposition of
a matrix using the generalized sign matrix, Appl. Math.
Comput., 8 (1981), pp. 237-250.
[10] J. Demmel and K. Veselic, Jacobi’s method is more
accurate than QR, SIAM J. Matrix Anal. Appl., 13 (1992),
pp. 1204-1245.
[11] J. Dongarra and D. Sorensen, A fully parallel algorithm
for the symmetric eigenvalue problem, SIAM J. Sci.
Statist. Comput., 8 (1987), pp. 139-154.
[12] P. Foldiak, Adaptive network for optimal linear feature
extraction, IJCNN, Washington DC, (1989), pp. I401-I406.
[13] J. W. R. Griffiths, Adaptive array processing, a tutorial,
IEE Proc., 130 (1983), pp. 3-10.
[14] Y. Huo and R. Schreiber, Efficient massively parallel
eigenvalue computation, Internat. J. Supercomput., 7
(1993), pp. 292-303.
[15] J. L. Howland, The sign matrix and the separation of
matrix eigenvalues, Linear Algebra, 49 (1983), pp. 221-232.
[16] I. Ipsen and E. Jessup, Improving the accuracy of inverse
iteration, SIAM J. Sci. Statist. Comput., 13 (1992), pp.
550-572.
[17] I. Ipsen and E. Jessup, Solving the symmetric tridiagonal
eigenvalue problem on the hypercube, Tech. report RR-548,
Yale University, New Haven, CT, (1987).
[18] S.M. Kay, Modern spectrum estimation: Theory and
Application (Prentice Hall, Englewood Cliffs, NJ).
[19] R. Klemn, Adaptive airborne MTI an auxiliary channel
approach, IEE Proc., Part F, 134 (1987), pp. 269-276.
[20] S. Y. Kung, Adaptive principal component analysis via an
orthogonal learning network, Proc. ISCAS’90, New Orleans,
(1990).
[21] S. Y. Kung and K. I. Diamantars, A neural network learning
algorithm for APEX, Proc. ICASSP’90, (1990), pp. 861-864.
[22] I. D. Lau, Linear algebra, Best-Wise, (1995).
[23] C.-C. Lin and E. Zmijewski, A parallel algorithm for
computing the eigenvalues of an unsymmetric matrix on a
SIMD mesh of processors, Tech. report TRCS 91-15,
Department of Computer Science, University of California,
Santa Barbara, CA, (1991).
[24] S. S. Lin and S. H. Hsu, A low-cost neural sorting network
with O(1) time complexity, Neurocomputing, 14 (1997), pp.
289-299.
[25] F.-L. Luo. and Y.-D. Li, Real-time neural computation of
eigenvector corresponding to the largest eigenvalue of
positive matrix, Neurocomputing, 7 (1995), pp. 145-157.
[26] C. Mead, Analog VLSI and neural systems, Addison-Wesley,
Reading, MA, (1989).
[27] E. Oja, A simplified neuron model as a principal
component analyzer, J. Math. Biol., 15 (1982), pp. 267-273.
[28] J. Rutter, A serial implementation of Cuppen’s divide and
conquer algorithm for the symmetric eigenvalue problem,
Tech. report UCB/CSD 94/799, University of California,
Berkeley, California, (1994).
[29] T. D. Sanger, An optimally principal for unsupervised
learning, D. S. Touretzky, ed., Advances in Neural
Information Processing Systems, 1 (1989), pp. 11-19.
[30] R.O. Schmidt, Multiple emitter location and signal
parameter estimation, IEEE Trans., (1986), pp. 276-280.
[31] R. Schreiber, Solving eigenvalue and singular value
problems on an undersized systolic array, SIAM J. Sci.
Statist. Comput., 7 (1986), pp. 441-451.
[32] G. Shroff and R. Schreiber, On the convergence of the
cyclic Jacobi method for parallel block orderings, SIAM J.
Sci. Statist. Comput., 6 (1985), pp. 853-864.
[33] Y. H. Tseng, High-order neural networks and it's
applications, The Department of Computer Science and
Information Engineering, National Taiwan University,
(1993), pp. 16-23.
[34] B. Widrow, Adaptive signal processing (Prentice Hall,
Englewood Cliffs, NJ).
[35] T. Y. Li, Z. Zeng, and L. Cong, Solving eigenvalue
problems of real nonsymmetric matrices with real
homotopies, SIAM J. Numer. Anal., 29 (1992), pp. 229-248.
[36] H. Zhang, T.-Y. Li, and X.-H. Sun, Parallel homotopy
algorithm for symmetric tridiagonal eigenvalue problems,
SIAM J. Sci. Statist. Comput., 12 (1991), pp. 469-487.