Randomized Strong Recursive Skeletonization: Simultaneous Compression and LU Factorization of Hierarchical Matrices using Matrix-Vector Products

Resumo Técnico: Esqueletização Recursiva Forte Aleatorizada

Enunciado do Problema
Matrizes hierárquicas ($H^2$-matrizes) sob a condição de admissibilidade forte oferecem uma estrutura para comprimir matrizes densas originadas de equações diferenciais parciais (EDPs) e equações integrais. Estas matrizes particionam interações em componentes de campo próximo (armazenados densamente) e de campo distante (aproximados por blocos de baixo posto), utilizando uma estrutura de base aninhada para alcançar complexidade de armazenamento linear e multiplicação matriz-vetor eficiente. Embora produtos matriz-vetor rápidos sejam bem estabelecidos, a inversão direta (fatoração LU) de $H^2$-matrizes permanece desafiadora, particularmente para problemas tridimensionais. Métodos de inversão existentes tipicamente requerem acesso explícito às entradas da matriz e dependem da recompressão repetida de blocos fora da diagonal durante o processo de fatoração recursiva. Além disso, obter uma representação $H^2$ para matrizes disponíveis apenas através de sua ação sobre vetores (configurações matrix-free) tem sido um problema em aberto, com abordagens aleatorizadas anteriores sofrendo de grandes prefatores ou exigindo matrizes de teste estruturadas que são difíceis de projetar dinamicamente.

Metodologia
O artigo introduz a Esqueletização Recursiva Forte Aleatorizada (RSRS), um algoritmo que comprime e fatoriza simultaneamente $H^2$-matrizes gerais usando apenas a ação da matriz $A$ e de sua adjunta $A^*$ sobre vetores. O método opera sob a condição de admissibilidade forte e evita o acesso direto às entradas da matriz.

A metodologia central baseia-se em dois componentes principais:

1. Esboço Aleatorizado com Matrizes Gaussianas Densas: Em vez de projetar matrizes de teste estruturadas com padrões de zero específicos (o que aumenta a complexidade de amostragem e requer conhecimento prévio dos índices de esqueleto), a RSRS emprega matrizes de teste Gaussianas densas $\Omega$ e $\Psi$. O algoritmo gera esboços iniciais $Y = A\Omega$ e $Z = A^*\Psi$.
2. Imposição Estrutural Dinâmica via Transformações Lineares: À medida que a fatoração procede recursivamente através de uma árvore hierárquica (do nível mais fino para o mais grosseiro), o algoritmo introduz a estrutura necessária nas matrizes de teste via pós-processamento. Duas operações principais são aplicadas aos esboços densos:
   • Anulação de Blocos: Computa uma base de nulidade para anular contribuições de índices de campo próximo, isolando efetivamente as interações de campo distante para compressão de baixo posto (Decomposição Interpolativa).
   • Extração de Blocos: Utiliza transformações de pseudoinversa para extrair subblocos densos de campo próximo necessários para os passos de eliminação.

O algoritmo aplica recursivamente um procedimento de "esparsificar-então-diagonalizar". Em cada caixa na hierarquia, ele computa uma decomposição interpolativa (ID) das interações de campo distante para identificar índices redundantes (esqueletos). Ele então aplica matrizes de eliminação de blocos para desacoplar esses índices do restante do sistema. Crucialmente, as matrizes de esboço ($Y, Z$) e as matrizes de teste ($\Omega, \Psi$) são atualizadas em cada etapa usando as matrizes de eliminação e esparsificação derivadas ($L, U, E, F$). Isso permite que o algoritmo mantenha esboços do sistema diagonalizado evolutivo sem nunca acessar entradas individuais da matriz ou redesenhar amostras aleatórias.

Principais Contribuições

• Inversão Matrix-Free: A RSRS estende a inversão de $H^2$ para configurações onde as entradas da matriz são inacessíveis, dependendo exclusivamente de produtos matriz-vetor. Isso amplia a aplicabilidade para operadores integrais solucionáveis via Métodos de Multipolo Rápido (FMM) ou FFTs, e para blocos densos originados de solvers de EDPs esparsas.
• Compressão e Fatoração Simultâneas: Ao contrário dos métodos tradicionais que separam compressão e inversão, a RSRS integra esses passos. Isso evita as estruturas de dados intensivas em armazenamento e as recompressões repetidas exigidas por abordagens anteriores, mantendo os blocos fora da diagonal atualizados em forma comprimida.
• Eficiência de Amostragem: O número de produtos matriz-vetor necessários ($s$) é independente do tamanho da matriz $N$ e depende linearmente apenas do posto máximo dos blocos fora da diagonal e da geometria do problema. O método alcança isso usando matrizes de teste Gaussianas densas genéricas, evitando os altos custos de amostragem associados a matrizes de teste estruturadas.
• Robustez: O algoritmo é projetado para lidar com matrizes indefinidas e mal condicionadas, como as originadas de equações de Helmholtz 3D, sem exigir que a matriz seja positiva definida.

Resultados Numéricos
Os autores validam a RSRS através de três experimentos numéricos:

1. Equação Integral de Volume 2D: Uma equação integral de Laplace de primeira espécie em uma grade uniforme. Apesar de a matriz tornar-se cada vez mais mal condicionada conforme $N$ cresce (número de condição $\sim 10^6$), a RSRS manteve baixos erros de compressão relativa ($10^{-7}$ a $10^{-6}$) e reduziu as iterações do GMRES de milhares para menos de 5 ao ser usada como um precondicionador.
2. Equação Integral de Contorno 3D: Uma equação de Fredholm de segunda espécie em uma esfera. O método demonstrou precisão estável e escalonamento linear no tempo de reconstrução, memória e tempo de solução em relação a $N$.
3. Complemento de Schur de Helmholtz 3D: Um complemento de Schur denso originado de um solver direto esparso para a equação de Helmholtz 3D. A matriz é indefinida. A RSRS comprimiu com sucesso o complemento de Schur, reduzindo as iterações do GMRES de não-convergência (mais de 10.000) para dígitos únicos (3–9) para vários tamanhos de problema.

Em todos os casos, o tempo de reconstrução ($T_{rec}$), o tempo de solução ($T_{sol}$) e o uso de memória escalaram linearmente com $N$, consistentes com a análise de complexidade teórica de $O(k^2 N)$ e $O(k N)$.

Significância e Alegações
O artigo afirma que a RSRS representa um afastamento significativo das técnicas tradicionais de inversão $H^2$ ao permitir a fatoração direta em ambientes matrix-free. Ao combinar compressão e inversão em um único processo recursivo impulsionado por esboços aleatorizados, o método oferece eficiência computacional competitiva e requisitos de armazenamento reduzidos. Os autores enfatizam que o uso de matrizes de teste Gaussianas densas, aliado a transformações lineares dinâmicas, elimina a necessidade de designs de matrizes de teste complexos e específicos para cada problema. O método é apresentado como um solver direto aproximado robusto, adequado para uma ampla gama de aplicações, incluindo equações integrais de contorno, discretizações de EDPs e quantificação de incertezas, particularmente onde as entradas da matriz são caras ou indisponíveis. O trabalho sugere que o efeito de feedback de usar esboços para definir as transformações que atualizam esses mesmos esboços é benigno na prática, permitindo uma fatoração precisa sem redesenhar amostras.