Praticamente a questão. Dada uma matriz geral esparsa e não simétrica (tanto numérica quanto estruturalmente), qual a importância do padrão de esparsidade (isto é, permutação de linha / coluna da matriz / vetor) para os solucionadores iterativos? Percebo que isso se torna importante para solucionadores diretos (LU) ou pré-condicionadores (ILU), afetando diretamente o número de preenchimentos.
Para solucionadores iterativos, no entanto, parece que a parte mais importante é a operação MatVec, que parece não se importar com o padrão de matriz real. Existe algum componente que possa depender do padrão que não estou considerando aqui?
Que tal em paralelo? Suspeito que o padrão possa se tornar importante na maneira como a matriz e os vetores são distribuídos e, portanto, determina o volume / sobrecarga de comunicação, mas gostaria de ver outros pensamentos e informações.
Estou perguntando isso em geral e também em relação aos solucionadores de KSP do PETSc.
fonte
Respostas:
O pedido é significativo apenas em equilíbrio de carga / comunicação e adequação ao pré-condicionamento. O método Krylov não se importa com o pedido ou mesmo se as entradas da matriz estão armazenadas.
Na prática, uma ordem incorreta pode exigir muito mais comunicação do que o necessário caso seja multiplicada por uma matriz. Veja a seção do Manual do Usuário do PETSc sobre "Pedido natural" versus "Pedido PETSc" para um exemplo. Além disso, uma ordem correspondente a uma partição paralela incorreta pode tornar os pré-condicionadores de decomposição de domínio menos eficazes. Observe que é a partição que importa aqui, embora uma partição induza uma (classe de equivalência de) pedidos.
fonte