`
`1\vlati�ix Co:n1.p11tations
`
`THIRD EDI'flON
`
`Gen.e FL G·olub
`
`Department of Computer Science
`
`Stanford University
`
`Charles F. \lan Loan
`
`Department of Con�puler Science
`Cornell UniverBity
`
`Thr, Johns Hopki11s University Press
`
`Ibltimore �nd London
`
`ZTE, Exhibit 1016-0001
`
`

`

`©]�iB). 19s,;;, i·�f�;::·-; Th�� John8 }{,;>r:kins l
`.!n�vc.::rshy Frt�ss
`•,.,;-;·\·c<
`.. Pt:bhbcd 1996
`All right� n,
`Pdr..ted i:! ti:-::: ��--::��
`'.::'d St��t{?':'.' of Ar.n�dca on nc!d�-frt'j�
`pup-<.�r
`9 8 7 6
`
`:'..\,t;i}oging-in-Pubik'.ation
`Daw will be found
`=::.r.,-,,
`· .. : .. :,:,:,
`
`• ':., ·� j •• ,;_
`
`•·:;,p••,'.
`
`ZTE, Exhibit 1016-0002
`
`

`

`
`
`CHAPTER 2. MA'i'lUX ANALYSIS
`
`2.a. ◊RTHOGONA!XfY AND THE SVD
`
`69
`
`
`
`mdoff error, Wt\ rncommeud
`
`RP. Brent. (1970). ''Error A11a.lysis of Algorithms for Mati-ix �.foltiplicatim, u,id T'dan­
`
`
`
`
`
`
`
`
`
`
`gulnr D«:ompO£lUon l;i,;ing \Vinograd'B Identity," Nv.m,ir. M,ith. 16, 145--lofj,
`
`
`
`
`W.Miller (1975), "Computational Complexity and NBmmic.-.J Stability/' SIAM .J. C(,m.­
`
`puting 4, 97-10'7.
`
`
`
`N,J. High,,m (1992). "Stability of a �fothtld for Mu!t.iplying Complex ,_,fot.rke;; with
`'l'hi-ee Rea!
`
`
`
`
`
`ll'!Mrix Anal. App;: 13, l58l·-1587. '.\fot.rlx Multip!icatio11s," .91.AIV! J,
`
`
`
`
`J.W. D<:,mmel and N.J. Higham (1992). ''8:,abllily cf Block Al
`
`g,,rlt.hrrn, with Past Leve\--3
`-is;' BIA.Al Review 1B, 548-u8.
`
`
`
`BLAS," AC'AJ 7hm.s. Mc.th. Soft. 18, 274---291.
`
`
`'um�:rical l\1ethod.s a-nd Sof/.warr:, Prer,tk:e--
`
`olve intervn.l analysis, the building of sta­
`
`Orthogonality and the SVD
`2.5
`
`
`
`
`
`
`Orthogonality hBs a very ptmnin�mt role to play 1n matrL'<{ cornpufations.
`ysis hselI:
`
`lWLillg of Ihe anal
`
`
`
`
`After establishing a few definitions WB prove the extremdy useful singu1ar
`.Pt·obabili1,tic Modds for Propagation of
`
`
`
`
`
`
`va1ue decomposition (SVD). Among other things: the SYD enables uti to
`
`
`
`
`intelligently hiu1dlt� foe matrix rank problem. 'X'he concept of rank, though
`
`
`
`1Jlat.ion of the Effects of Roundnff Errors,.,
`
`
`
`
`
`perfoctly clear in the exact arit.hmetk context, is trkky in the ptesen<:e of
`
`
`
`
`roundoff error and fuzzy data, '\Vith th{� SVD we can intrnduce the practical
`
`
`notiori of numerical rank
`
`=
`
`=
`
`=
`
`::1:
`=
`
`.iint nel.lds a tlwrnngh undr.1:st,mding of
`
`
`Orthogonality
`2.5.1
`
`
`
`
`: Mquirinf; knowledge in. this dlrec.tion \.�
`
`p} in. JR'"' is orthog onal if x{ :z:
`0 whenever
`
`A set of vectors {x1,, \., :i:
`I in
`:i
`
`
`-i l- j and orthonoruwl'=· if xf:1:j l>iJ• Intuitively,
`
`
`orthogonal vectors are
`
`
`Scientist Should Know About Floating
`
`
`
`
`
`maximaUy independent for they point i:n totally different directions.
`S1, .• , , Sp in m?n is mut·1wll
`
`A collection of subspaces
`
`r1 orthogonal if
`
`
`
`
`rs:7 y 0 whenever :i; E Si and y E Sj for i # j. The orthogonal compkrnent.
`
`of a subspace S � 1rrm is defined by
`slon Arithmetic Pr.cir.age," A C!V 1hms.
`
`
`
`,r<n Mu!t.\ple Pa�ision Arithmetic Pack-­
`
`
`thlnty of Num,irical Software," SIAlJ.,f J.
`and it is n<it ha-rd to show tha.t ran(A)J.. ""'rmU(..tf
`
`1, ... , t?fo
`r). ThEi ved;orn -v
`
`
`
`form an orihcmormal basis for a subspace S � JR"' if they ate orthonormal
`
`
`e ArithrneUc of the Digital Computer,"
`and span S,
`
`{AR: A Subr-:)utine to DynamicaJly De-­
`A matrix Q E 111rr,xm is sa.kl
`to be) ortJwgonoJ, if Q'l'Q I. If Q
`
`U, 303-311.
`Afal.h.
`Soft.
`
`
`[ ,11, . , , , <Jm ) is orthogonal, then the (Ji form an arl:hm,ormal bwL"I for Jitn,
`
`
`,uts (H}89), "Floatfog PniJ;t, Arithmetic
`
`
`
`
`It ls always possible to extend such a basis to a full (Jrthonormal basis
`
`rnputing A ;r,plc 3, 86---ilil.
`'':
`{v1, � ..
`1 �u,.,i} for JR!
`
`
`sion 1r,�-ill:ili.•.ti-::m and Exenition of FOR-
`19, :zsg .. 319,
`Theorem 2.5,l If
`
`
`of high-quality soft.wm·e, even for '"slm­
`Vi E JI-rx(n-r) such that
`
`
`: the design of a subro,.itine ;;a comp1Jt.e
`V={ViVi]
`
`
`
`S;,. "" {y E JI{'n : �;r 0 for ;:1,jj x E S}
`
`=
`
`=
`
`
`
`Vi E If'x;-- has on'.lwnormal cvlumm.s, then them e:1:iBts
`
`
`
`
`
`gram to FlnJ tJw Etwllde,�n Nnrm of a
`
`Proof. Thls is a standard result frorn introdnr.tmy lhiear algd)ra., It is
`
`
`
`her "fast" lineal' alg,;brn. proce<Jurei,;
`!lr?ll
`
`
`
`thH.t 'SVe present in �fi.2. CJ also a comllary or the QR fadori:1;ation
`
`ZTE, Exhibit 1016-0003
`
`

`

`'!O
`
`
`
`CHAP,'ER 2. Iv1ATlUX A':< ALYS!S
`
`
`2.5. 0R!TiOGONAUTY ANI
`
`Norms and Orthogonal Transformations
`tJ{insform>.ttion, for
`if qrq ""' l,
`.hogonal
`inv,i.ria.nt
`nndex o:rt
`The 2-norrn b
`'T' ,,"·o ·r I' ... , ,1·,1 · 2 d
`'l<" "''at·e·.v .
`i l""' : 1 , . .,. ,.
`l ·1 .,, 11·'
`.. ,i {:.,,.,.,
`'•J.
`••-
`,.,, ... � ... J>..J'. .......
`Av,
`..,.,..,
`: >.tJ 1:::
`,.,:, • .:.,
`....,..,, j
`:J.;' t.J' ,,.. .. _ ,.,, . ,., - : ,,. :: �
`,_
`.;"',{./
`-.::
`'SJI
`-''OJ:'l''
`•, -.,,..,�
`:i ·�:,._,(._; )1
`tlw Fi-di(m\us nonn &re a.foo inwnfant. vv'ith re;,ped. to
`transfor­
`orthogona.l
`.41·n,
`1n pn.rt.ieuhw, it l.s ern,y to show tl:wt for ,ill orthogonal Q
`and Z
`niatlons.
`dim{!milot1s w;� luwe
`
`It i;; convenfont to bwe the f
`of >.i.pprnprh:te
`1ms;
`
`V
`
`= jlA!ir
`ilQAZll
`p
`
`(25.2)
`
`oi(A) -· Ui
`trm.;,:.: (A)
`,_ th
`<'.lmi.n(A)
`-··
`th
`
`values of ,t matrl
`The t,ingob.r
`2,5.3 The Si.H[?;ulur VtiJue Decomposition
`
`
`psoid .l!J defirH�
`cf t.}1� hyperelH
`
`
`in the prtivious two tll'K'.t:iorn:; om be used t,) The Ui<,,ory of uorn1s developed
`
`
`
`
`pr�.-,w the {\Xtr.emdy useful singnfa.r value decomposition.
`
`
`
`Theo:rmn 2.5.2 (Singulaa· VahH,! Decomposition (SVD)) .lfA i,q a rwl
`rn--by ... n, rna.tri ...
`
`1:) then. there e�tist or1hogon{f.1 rn.,atri{.�r-:,!�
`arid v· "" ['Vi,,.', 'V,.-,] E Jf·C·Xn
`
`snch dud
`
`.96
`�L�::g
`
`The SVD revea.ls a. f�re;.'\.t <
`
`
`SVD of A io given by Tieormx
`
`{1 ·u/r l
`0 13 J ---A;.
`UTAV f
`l
`
`...
`
`rank(A)
`null(A)
`ra.n(A)
`
`.A=
`
`Voriou,; 2-xwrm and Frnbenit
`
`D ii:
`l]Ai ([ .:,
`SVD. lf A E :iR:""'", then
`!1:? > fo·2 .; ... ,,,
`'1 "'' '
`., A i:2
`,', A Jl1 "" II A
`1 ,i,I� &'lU' l'\O V'�'
`T-wi BFt ""
`we J·,"ve :I ,1-
`,;al j '" � 4,,.
`.. .,
`. '
`., �;
`: t�_,-
`.
`.r.,
`.
`!, Hp
`., -"-.!,. ; �· .:.,.... \
`:,.;._, ' :;
`B.rg-umenL compl!�tes the
`proof of
`induction
`haw� w "� D. An ohv1ous
`rrnrnt:
`the theorem. u
`/iAJh
`j/A:i;/)
`min
`The O'i am the singular Dalu.e8 of A and the vectors 1.1.i a.nd ·1..1i ?l.rn the
`
`
`
`
`(.
`. H :i: Ji:,
`;"t:'�{J
`
`
`
`
`ith left sinag[ar vector a.nd the it:h right Hingnlar wiclor reBpective'ly. It
`
`2
`
`ZTE, Exhibit 1016-0004
`
`

`

`'ransfort:nations
`
`qro .
`
`•
`
`t,
`
`.
`.
`
`:tvfxnux AJ<A
`.: .. ·
`!APTER 2.
`.
`
`7l
`Li:i. ORTHOGONALITY
`AND TEE SVD
`'.5 em,:v to v�)rify by
`comparing
`colunms
`in the (-,q,rntions
`AV -·
`A 'I' U '"' VY.;
`T foat
`r,urnfonna,tion. for if
`' ' ' J
`, ... lj � rr'l
`:J.. i.2 . . w mat:nx 2--noun
`,:,.
`_A1;i "" i'.L(Ui
`AT U; .... (t,t!; } ·i :z; 1:min{m.,,
`n}
`rnspect
`to orthogonal
`tran<
`ttEJ.t
`for nil mthogmHil
`q a,>'.
`:� is
`conv�ml.ent.
`to hu:ve thi following
`noto.tion
`.for desigrniting
`singnhr va.l­
`•i�,s:
`the ith large,<:t
`singular value
`of A,
`... the hugest singu1a1· value of
`A,
`u.,,w,.(A.)
`the smal1e1;;t
`singnh:u·
`v«-lne of
`A.
`i1mir:.(A) �
`.xes
`The i,ingul
`ar values
`of a nwtr;x A are
`prndsely
`the lengths of the semi-a
`l } .
`>t the hypm·dlipsoid
`E defined by E :z; { Ar : li :i: i! 2
`)HS tvlo :sectio1u•�
`cH.:n
`be usE.;d --:
`lCOmpo:iition.
`l f ,8 .fi
`r ') 0
`L 2.23 .f1{; .l -
`l lJL,'V
`A:=
`}\ ,f; l0 1 .6 --.8
`iµoaithm (SVD)) If
`Ai.&{!<.
`l i!
`[.6 -.8
`f
`rrmt1'i{:.f.!j
`l
`· = [ -u1 v 1 ,::: 1nnxn
`The SVD reveals
`a grne.t
`deal abrn1t the strndure of a mn.t.'ix.
`If the
`SVD of A is given by Theorem
`·2.5.2,
`imd we define
`r by
`
`{2.�·
`
`mposition
`
`1 ' • • � n � ... _ .ttt.r
`
`Example 2�5�1
`,tH3 J.72 ;
`r
`
`T
`�!-:
`
`=
`
`; L
`
`J
`
`p&,n{t1r+1,
`,., ,v,.}
`=
`1, .. , ,ur},
`spm1{,t
`
`(2.5.:3)
`('2.5.4)
`(2.f).5)
`
`r s
`
`� '
`
`-.�
`.:. l
`
`•:i c• ,.
`( .,,;. �-
`
`rank(A)
`?xrn. ve<:.tors
`Ui�t sat.isl\, A:r '·"
`null(A.)
`�iler<:l exist Vi
`i c 1R:"s:(n-1) �i.nd
`ml u ;:::; f ·11 U,, l .:
`lH:" X ,;·,.
`r;--u1(/I)
`i. F hm; the following structure:
`'·••· .d.:,
`
`(2,5.6)
`A
`Various 2--norm
`arid Frobenhrn
`norm properties
`hu:ve conn.edfong t0 the
`1Rm x '1, then
`If A. E
`S\/fJ.
`l A HB
`ii A.1 ii� , and so we
`I. , r"
`i /1 r;.,
`;ument cornpletPs the proof of
`\j;b:\12
`minxf.O
`. the vectors ·u.
`., H:t1d 1;i gn, the
`, , mg,wxr wx:trJr
`" ___ .} __ _
`respectively.
`It
`Ii X Jhi
`
`=
`
`li A i:2
`
`(2.t�.8)
`
`(m?:: n). (2.15,9)
`
`ZTE, Exhibit 1016-0005
`
`

`

`310
`
`7. L PROPEK!TBS AND 1
`------------···-··-·-------
`.:;;.re referred to as eigent•e(
`
`
`LAPACK: Um;ymmet.ric Eigenproblm:n
`~ GEBAL Bi,lam.:e t,nmsform
`lf Aa: = >.:i: and a left eig,
`_GEB1\K Und<) bala-nce tra.nsfonn
`
`"eigenvector" mea.rrn "rigl
`1 AV"" ll
`_@1mD Hes.-,imberg reduction U'
`
`An elgenvect.or defines
`
`_or.MM U (fact<:m0<.l form) times matl'i-'< (n1al G:J.:::e)
`respect to preniultiplicatl,
`_ ORGmt Gm-iemtf!S U { re«l cac;;i)
`
`t!w property that
`
`��l'lllltV ( factor<,xl form) times matrix { eomplex <:i;;,e)
`!, ..
`,_ .. _m_,_a_m_t.....,""""G"'eueratoo U (,,r,mpl0,'<
`eai,;_e�)
`_________ _
`! _ HSEQR Sdmr cJ1..,composltJ,m. of Hessenbtirg rrnitrix
`
`
`ls @-id to be in:variard {fo
`!-.:_HSEIN
`
`
`Eigenvector;; <>f Hessenberg matrlx by inverse lterat.icn_i ______ .........-:
`i .. GRES
`Schur doe◊ltl}'.;�;_r genern.l matrix with o, vahi<i .,ord;;,fiig
`i _ i.lEESX Sa.me but with <:onditlon estlmat.es
`·-<lEEV
`Eigenvah;e,;; and ldt and xi�ht. eig1;mvect.orn of genar;:,,l nmtrix
`then ra.n(X) is invarlant 1
`l_GEEVX SilX(lf.l but with cor.difam r,stirrlli.tfls
`Sel�:teci eigimv&:t�)i·s of ur-,p-e_x_q_u_s_s-it-r
`.,,lat"--m-a-t.-ri.Jc--
`"'k-\r-
`1g-11
`j .. TREVC
`foll column rnr.k, t,hen A)
`u. TRSW\ Cowl estiimi.t,31,
`of il!lle-cted eigeuvalue,; of upper qua$itl'iang11h·w matrix
`:,n.<l nonsingufa.r, then ,\(,
`TREXC Unita1·y r.eordic!ri?lg of Sd-air deu,1ts1posltimi
`_Ji
`::.re similar. In this (:ontm
`'l'RSEil Ssxr,e but with ,�onditi(rn estimntns
`TRSYL Solve$ A...-Y + X B "'. C. for _upper q:rn;;ltrlangu\m: .4 and B
`
`......... ·-··--·-
`Decoupling
`
`[i�4-PA?K: Unsymmeti-k, Genei·alfa:ed Eigenpi·oblmn
`\J.imy eigenvalue compuh
`! _ GGBAL J3al2.nce tzansform
`i .. GGHaD
`
`
`;;1,,0 a collection of smalh.i,
`Reduct-km. to H.ei;senberg�Triangul;u- fnrm
`1 .. HGEQZ
`
`
`Cenerll.lfa1> .. d Sdmr <lecorupositkm
`'.<:;;-these reductions.
`i .. TGEVC Elgenvectoi-s
`[;11
`t:ndc h,,Jarice t;:;mi,forra
`l .. GGBAK
`.Len:nrm 7. L 1 If '1' E
`
`Properties and Dettornpositions
`7.1
`'
`
`
`In this sedion we survey the mathematical back,_;;,;ro1md necessary to develop
`
`
`and analyze the eig(m.vaJue algorithms that fo11ow.
`
`Proof. Suppose
`7.l. l Eigenvalues and Invariant Subspaces
`Tx = [
`Tht, eigenvalues of a ixrn.trix A. E (i'.
`
`nxn are the n roots of lki chm-r.tcterfatic
`potynO'mia.l p(z) "" det(zl �- A.). The set oftlwse roots is called the sped:rnm
`
`·.=:here �r1 E (fJV and :1>2 E �
`
`
`and is denoted by ,\(A), If ,\(A)"" {.\1, .. , then it fo1lo•Ns tha.t
`,.\;J,
`
`· .1:n), If :rz = O, then �
`det(A) ""' .1\1 ),2 • • • -><n .
`
`T) C A(T, 1) u ,\('.l'.22), E
`
`,.,,me cardinality, the two
`Moreover, if we defimi the tmce of A. by
`
`tr(A) z:, L.::0+i,
`
`·n
`
`The Basic l
`::,.-using tiimHarity tnrnsfr
`
`then tr(A.) :::: A>.,,, This folfows by looking at the eoefHdent of
`1 + · •, +
`t,D.y one of severn,1 earn
`
`
`z11·~1 in the cha.rnderl.stic polynomial.
`displi.w the eigmrvalu,
`
`If .\ f::. ), (A.), then the nonzero vectors :r E-: (1;11 that satisf:v
`: :-, th.at they provide. E
`
`
`: :,,:ussirig the reductions 1
`
`i,:;,-'...:.l
`
`ZTE, Exhibit 1016-0006
`
`

`

`7'. L PROPERTIES ANO DECOMPOSlTJONS
`
`,,re referred to as eige.·irnectors. More preci.seiy, :r is a right. eigenvector for ,\
`
`
`;f fi.x ,,, ).x and a left ei_qe1wecto, if xothenvise stat,d, H.A = Ai.!1• Unless
`
`"eigenvector" means «right eigenvector."
`An eigenvector defines a·one-dhnensional subspace that is invariant with
`respect to premultip!ica.ti.on by A Morn genera.Hy, a subspace S ;; (G" with
`
`th<:\ property that
`
`x ES=¢- Ax ES
`is sajd to he w.vadant (for A). Noto that if
`
`AX,,, XB,
`
`g inatr_ix
`: by invei-,m
`ittu:atlon
`itii' e. w.hw m:dmfog
`
`then rnn(X) ls invariant a.nd By"'" ),;y A.(Xy) = >.{Xy). Thus, if X has
`
`
`
`full column rnnk, then AX 0,, XB implies that ,\(B) C A(A). 1f Xis square
`sittiangu[ar rni,t.rix ···-·--··
`1.1x
`
`�Jues of up.!}€'.r qu11;;1tdan,;ular matrix
`
`ll.nd nonsingular, then >.(A) >.(B) and we say that A and .B = x-
`positlon
`
`am Bim'ilar. In this context1 X is caHe.d a similarity transfarnw.tfon.
`
`iasilt.r.iangular A and B
`-----.:
`
`*
`
`=
`
`;
`
`·kj.nguia::.� fnrrn
`
`sition
`
`7.1.2 Decoupling
`Many eigenvaJue computations involve breaking the given problem down
`
`
`into a �olhx::tfon of smaller dgenprobleirw. I'k1 follmving result is thi bru;is
`
`for these reductions.
`
`
`
`--�----···-�---'
`
`Lemma 7,1.1 If TE C'\"'1 is partitionf'.d f.W follows,
`
`:nnpositions
`background necessiU'v to devdnn
`.. •
`.t. follow.
`then A(T) "">.(Tll) LJ >.(T:n).
`Proof. Suppose
`
`,..,,, l p,. l2
`f I
`Tn
`'1' -�
`0
`J T22 q
`1
`L
`{J
`p
`
`;nt Subspaces
`, t.he n roots of its ch<1,ra,cterisl:ic
`
`these roots is caHe<l the spectrum
`, ),n}, then it follows that
`wlwre XJ. E {If and :t>4 E (L"!, If :t2 ): 0, Hien T222:2 = ..\;:r:2 and so >. E
`
`
`
`
`,\('.Ib). If ;:i:2 "" O; then 111:r1 = >,�-r::1 and so .\ E ,\(Tu). It follow,i t.h,tt
`
`-\(1') C ..:\(T11)UA(122),. But since both .\(T) a.nd >.(T11)u>.(T22) btve the
`
`Sf\-nH: card.hrn.Uty, the t:\!'10 sets a.re aquaL O
`
`.,
`
`7.l.3The Basic Unitary Decomposi.ti.ons
`
`
`By using shx1H.i.rity transformations, it is possible to re<luce a given matrix
`by looking at; the coefficient of
`
`
`
`
`to any one of several canonical fornu,. The canonical furms differ ln how
`
`
`t:hey display tho eigenvalues and in the kind of invariant sub$pace informa-­
`
`
`tion that they _provide. Because of their numetkal stability we begin by
`slmilMity.
`discussing the reductions that can be ad1ievod with u11itar)r
`
`
`
`: E {l�n that satisfy
`
`
`
`m::,:�••·"::��... . ... �..,,,....� ..... ..,... ...... •.•··· .. �·-····· - -
`
`ZTE, Exhibit 1016-0007
`
`