Vi studerar en iterativ matris konditionering algoritm på grund av Osborne (1960). Målet med algoritmen är att omvandla en kvadratmatris till en balanserad matris där varje rad och motsvarande kolumn har samma norm. Den ursprungliga algoritmen föreslogs för att balansera rader och kolumner i L2-normen, och den fungerar genom att iterera över att balansera ett radkolumnpar i fast rundrobinordning. Varianter av algoritmen för andra normer har studerats och implementerats som standardförkonditionatorer i många numeriska linjära algebrapaket. Nyligen, Schulman och Sinclair (2015), i ett första resultat av sitt slag för någon norm, analyserade graden av konvergens av en variant av Osborne algoritm som använder Lě norm och en annan ordning att välja radkolumn par. I denna uppsats studerar vi matrisbalansering i L1-normen och andra Lp-normer. Vi visar följande resultat för alla matris A = (aij) 1. Vi analyserar iterationen för L1-normen under en girig balansgång. Vi visar att det konvergerar till en -balanserad matris i K = O(min { −2 log w, −1 n 3/2 log(w/ )}) iterationer som kostar totalt O(m + Kn log n) aritmetiska operationer över O(n log(w/ ))-bit nummer. Här m är antalet icke-noll poster av A, och w = i,j  och amin med amin = min{ och aij = 0}. 2. Utgångspunkten är följande: Vi visar att den ursprungliga round-robin implementeringen konvergerar till en -balanserad matris i O( −2 n 2 log w) iterationer totalt O( −2 mn log w) aritmetiska operationer över O(n log(w/ ))-bitar. 3. Vad är det som händer? Vi visar att ett slumpmässigt genomförande av iterationen konvergerar till en -balanserad matris i O( −2 log w) iterationer med hjälp av O(m + −2 n log w) aritmetiska operationer över O(log(wn/ )))-bitar. 4. Vad är det som händer? Vi visar en lägre gräns för konvergensgraden för varje genomförande av iterationen. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Vi observerar, genom en känd trivial minskning, att våra resultat för L1 balansering gäller alla Lp norm för alla ändliga p, på bekostnad av att öka antalet iterationer med endast en faktor av p.
Efter att tidigare versioner av den aktuella artikeln Sinclair 2015a, 2015b] gav REF en konvex programmeringsbaserad analys av L1-varianten av den iterativa algoritmen.
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}