Sammanfattning av denna webbsida: Randomiserad provtagning har nyligen visat sig vara en mycket effektiv teknik för att beräkna ungefärliga faktoriseringar av matriser som har låg numerisk rang. Detta dokument beskriver en utvidgning av sådana tekniker till en bredare klass av matriser som inte själva rang-brist, men har off-diagonala block som är; specifikt, klass av så kallade Hierarkiskt Semi-Separable (HSS) matriser. HSS matriser uppstår ofta i numerisk analys och signalbehandling, särskilt vid konstruktion av snabba metoder för att lösa differentialekvationer och integralekvationer numeriskt. HSS-strukturen medger algebraiska operationer (matris-vektor multiplikationer, matris factorizations, matris inversion, etc.) ska utföras mycket snabbt, men endast när HSS-representationen av matrisen har konstruerats. Hur man snabbt beräknar denna representation i första hand är mycket mindre väl förstådd. Detta papper visar att om en N × N matris kan appliceras på en vektor i O (N ) tid, och om enskilda poster i matrisen kan beräknas snabbt, sedan under förutsättning att en HSS representation av matrisen finns, kan det konstrueras i O (N k 2 ) operationer, där k är en övre gräns för den numeriska rangen av off-diagonala block. Poängen är att när äldre koder (baserat på t.ex. den snabba multipolmetoden) kan användas för den snabba matris-vektorn multiplicera, den föreslagna algoritmen kan användas för att få HSS representation av matrisen, och sedan väletablerade tekniker för HSS matriser kan användas för att invertera eller faktor matrixen.
Martinsson REF använder till exempel slumpvis provtagning för konstruktion av HSS-matriser, där element provtas från matrisen med multiplikationer av matriser.
A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
{'venue': 'SIAM J. Matrix Analysis Applications', 'journal': 'SIAM J. Matrix Analysis Applications', 'mag_field_of_study': ['Mathematics', 'Computer Science']}