Resumo Técnico: Métodos Baseados em Embeddings para Predição de Desempenho de Solvers Lineares

Definição do Problema

A solução de sistemas lineares grandes e esparsos é um gargalo de desempenho primário em aplicações de computação científica, particularmente aquelas oriundas de equações diferenciais. Embora bibliotecas modernas como o PETSc ofereçam inúmeras configurações de solvers e precondicionadores, não existe uma "bala de prata" única; as escolhas ideais dependem fortemente de instâncias específicas do problema, propriedades da matriz e ambientes de hardware (ex: paralelização, aceleradores).

As estratégias baseadas em dados existentes para seleção de solvers enfrentam três limitações principais:

1. Dependência de Características Caras: Muitas abordagens dependem de características numéricas custosas (ex: informações espectrais, estimativas do número de condição) que são computacionalmente caras de calcular, anulando os benefícios da seleção automatizada.
2. Escopo Limitado: Trabalhos anteriores frequentemente restringem seus conjuntos de problemas (ex: apenas matrizes simétricas definidas positivas) ou falham em generalizar através de diversos cenários.
3. Métricas de Avaliação Inadequadas: Métricas de classificação padrão (ex: acurácia) tratam todas as classificações incorretas como iguais. Elas falham em distinguir entre a predição de um solver subótimo, porém eficaz, versus a predição de um solver divergente, o que é crítico para a utilidade prática. Além disso, frequentemente ignoram o ranking de desempenho relativo dos solvers.

Metodologia

Os autores propõem um framework baseado em embeddings modular e de baixo custo que desacopla a modelagem de desempenho da representação de características e da predição downstream. O pipeline consiste em quatro estágios distintos:

1. Seleção e Extração de Características

O framework utiliza um conjunto de características numéricas baratas (computáveis em tempo $O(N)$ ou $O(nnz)$, onde $N$ é o número de linhas e $nnz$ é o número de elementos não nulos).

• Seleção: O esquema de seleção de características "all-relevant" do Boruta é aplicado para identificar características que performam melhor do que suas contrapartes "shadow" embaralhadas aleatoriamente.
• Exclusão: Características custosas, como estimativas diretas do número de condição, são explicitamente excluídas para garantir baixo overhead de inferência.
• Resultado: Um conjunto de características reduzido é derivado, contendo propriedades como dimensões da matriz, padrões de esparsidade e estatísticas de norma, mas excluindo estimativas espectrais caras.

2. Aprendizado de Embedding (Fase Offline)

Em vez de aprender um mapeamento direto de características para o desempenho do solver, o framework aprende um espaço vetorial de desempenho de baixa dimensão.

• Fonte de Dados: Os embeddings são aprendidos unicamente a partir de dados de desempenho observados (scores derivados de tempo de execução e valores de resíduo) através de um conjunto de treinamento de matrizes e configurações de solvers.
• Mecanismo: Matrizes e solvers são tratados como tokens em um vocabulário. Usando modelos como Word2Vec (skip-gram com amostragem negativa de amostras) ou GloVe, o sistema aprende embeddings onde a proximidade geométrica reflete a similaridade no comportamento do solver.
• Objetivo: Pares matriz-solver eficazes são mapeados para vetores próximos, enquanto pares ineficazes são separados. Isso captura relações complexas entre matrizes e solvers que não estão explicitamente codificadas em descritores numéricos.

3. Projeção (Fase Online)

Para uma nova instância de problema $x'$ não vista, o framework deve mapeá-la para o espaço de embedding aprendido sem retreinar.

• Combinação Linear: O vetor de características reduzido da nova instância é aproximado como uma combinação linear esparsa e não negativa dos vetores de características de treinamento ($\hat{f}(x') \approx \alpha \cdot F$).
• Mapeção: Os mesmos coeficientes ($\alpha$) são aplicados aos embeddings de treinamento ($G$) correspondentes para gerar a projeção $\hat{g}(x') = \alpha \cdot G$.
• Restrição: A projeção é restrita a coeficientes não negativos para interpretabilidade, e uma regressão linear padrão é usada para alcançar esparsidade sem penalização adicional.

4. Predição

O embedding projetado é alimentado em um preditor downstream para determinar a adequação do solver.

• Algoritmo: Um algoritmo simples de $k$-vizinhos mais próximos (k-NN) opera diretamente no espaço de embedding.
• Saída: O sistema trata o problema como uma tarefa de classificação multilabel, prevendo um subconjunto de solvers promissores em vez de um único rótulo. Isso permite uma avaliação baseada em ranking.
• Métricas: A avaliação foca em métricas centradas no usuário:
  • MAPE (Erro Percentual Absoluto Médio): Mede a lacuna de desempenho relativa entre o topo da predição e o solver ótimo.
  • nDCG (Ganho Cumulativo Descontado Normalizado) & LRAP: Avaliam a qualidade da lista ranqueada de solvers preditos.
  • 1-erro: Mede a frequência com que o solver ótimo está ausente do conjunto predito.

Principais Contribuições

1. Arquitetura Desacoplada: O framework separa explicitamente o aprendizado de embeddings do espaço de desempenho da projeção de características de matrizes não vistas. Esta modularidade permite que componentes individuais (conjuntos de características, modelos de embedding, preditores) sejam trocados sem retreinar todo o pipeline.
2. Inferência de Baixo Custo: Ao depender de características numéricas baratas e de um passo de projeção linear, o método evita o overhead computacional da extração de características caras (ex: análise espectral) durante a inferência.
3. Formulação Multilabel: O problema é formulado como classificação multilabel, permitindo a predição de um conjunto de solvers "bons o suficiente" e facilitando o uso de métricas de ranking (nDCG, LRAP) que refletem melhor as necessidades práticas de seleção de solvers.
4. Avaliação Centrada no Usuário: O estudo prioriza métricas como MAPE e 1-erro sobre a acurácia simples, reconhecendo que um solver ligeiramente subótimo é frequentemente aceitável, enquanto um solver divergente é catastrófico.

Resultados Experimentais

O framework foi avaliado em 621 matrizes da coleção SuiteSparse através de 101 configurações de solvers do PETSc (incluindo métodos de Krylov e precondicionadores como BoomerAMG, ILU e ParaSails).

• Desempenho com Características Completas: Ao incluir características numéricas caras, a abordagem baseada em embeddings alcançou um aumento de 17% na acurácia da top-predição sobre modelos clássicos baseados em características. Reduziu o MAPE em 37% e o 1-erro em 46%.
• Desempenho com Características Reduzidas: Mesmo quando restrito ao conjunto de características de baixo custo (excluindo estimativas espectrais caras), a abordagem de embedding permaneceu competitiva com modelos clássicos treinados com conjuntos de características completos.
  • Alcançou aproximadamente 24% menos MAPE e 24% menos 1-erro comparado às baselines clássicas em uma ampla gama de problemas.
  • Para o score estrito de "tempo-resíduo", o modelo de embedding reduzido reduziu o 1-erro de ~90% (Random Forest) para ~58%.
• Robustez: O método proposto falhou em prever um solver convergente em menos de 10% dos casos e superou consistentemente a configuração padrão do PETSc.

Significância e Alegações

O artigo afirma que os embeddings aprendidos podem efetivamente substituir características de matrizes caras para a seleção de solvers, mantendo o baixo complexidade do modelo. A significância deste trabalho reside na:

• Escalabilidade: A abordagem oferece uma alternativa escalável à classificação direta baseada em características ao minimizar o overhead de inferência.
• Generalização: O design modular suporta diferentes mecanismos de predição e critérios de avaliação, tornando-o adaptável a diversos cenários de problemas.
• Utilidade Prática: Ao focar no desempenho relativo e na predição multilabel, o framework alinha-se mais de perto com as necessidades práticas dos usuários de computação científica, que frequentemente requerem uma solução "boa o suficiente" em vez de uma teoricamente perfeita.

Os autores observam que a eficácia do embedding depende da diversidade e cobertura dos dados de treinamento. Eles sugerem que trabalhos futuros poderiam explorar mecanismos de projeção não lineares e estender o framework para predição consciente de hardware e tarefas numéricas mais amplas (ex: mínimos quadrados ou solvers não lineares).