Den symmetriska eigen value sönderdelningen och den singulära värdenedbrytningen (SVD) är grundläggande matrisnedbrytningar med många tillämpningar. Konventionella algoritmer för beräkning av dessa nedbrytningar är suboptimala med tanke på de senaste trenderna inom datorarkitekturer, som kräver att kommunikation minimeras tillsammans med aritmetiska kostnader. Spektral klyfta och konquer algoritmer, som rekursivt frikoppla problemet i två mindre subproblem, kan uppnå båda kraven. Sådana algoritmer kan konstrueras med polar nedbrytning spelar två viktiga roller: det bildar en bro mellan den symmetriska eigendecomposition och SVD, och dess anslutning till matris teckenfunktionen naturligt leder till spektral-avkoppling. För att beräkna den polara nedbrytningen är de skalade Newton och QDWH iterationer två av de mest populära algoritmerna, eftersom de är bakåt stabila och konvergera i högst nio respektive sex iterationer. Genom att följa detta ramverk utvecklar vi en högre ordningsvariant av QDWH-reningen för polarnedbrytningen. Den viktigaste idén med denna algoritm kommer från approximationsteori: vi använder den bästa rationella approximanten för den skalära teckenfunktionen på grund av Zolotarev 1877. Algoritmen utnyttjar den extraordinära egenskap som erbjuds av skyltfunktionen att en höggradig Zolotarev-funktion (bästa rationella approximant) kan erhållas genom att på lämpligt sätt komponera funktioner med låg grad Zolotarev. Detta låter algoritmen konvergera i bara två iterationer i dubbelprecision aritmetik, med den enorma graden av konvergens sjutton. De resulterande algoritmerna för symmetriska eigendecompositioner och SVD har högre aritmetiska kostnader än QDWH-baserade algoritmer, men är bättre lämpade för parallell databehandling och uppvisar utmärkt numerisk bakåtstabilitet. 1 1 Den tvåstegskonvergensen av Zolo-pd antyder att den kanske borde betraktas som en direkt snarare än en iterativ algoritm: även om det är känt [20, 21] att Abels omöjlighet teorem innebär att den exakta polar nedbrytningen inte kan beräknas i ett begränsat antal aritmetiska operationer, en approximation korrekt till O(10 −16 ) kan erhållas.
Newtons iteration och dess många varianter (t.ex. REF ) ger rationella approximationer till matrisen tecken funktion i motsats till polynom approximationer.
Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions
{'venue': 'SIAM Review', 'journal': 'SIAM Review', 'mag_field_of_study': ['Mathematics', 'Computer Science']}