¿Es importante el patrón de dispersión de un sistema lineal para los solucionadores iterativos (KSP)?

8

Más o menos la pregunta. Dada una matriz general dispersa, no simétrica (tanto numérica como estructuralmente), ¿qué importancia tiene el patrón de dispersión (es decir, permutación de fila / columna de matriz / vector) para los solucionadores iterativos? Puedo ver que se vuelve importante para los solucionadores directos (LU) o los preacondicionadores (ILU) al afectar directamente el número de rellenos.

Sin embargo, para los solucionadores iterativos, parece que la parte más importante es la operación MatVec, que no parece preocuparse por el patrón de matriz real. ¿Hay algún componente que pueda depender del patrón que no estoy considerando aquí?

¿Qué tal en paralelo? Sospecho que el patrón podría volverse importante en la forma en que se distribuyen la matriz y los vectores y, por lo tanto, determina el volumen de comunicación / sobrecarga, pero me gustaría ver otros pensamientos y entradas.

Estoy preguntando esto en general y también con respecto a los solucionadores KSP de PETSc.

linear-algebra petsc iterative-method mmirzadeh
fuente
1
Solo debería haber un problema en paralelo si tiene una gran cantidad de nonzeros en una fila o columna. Una matriz de punta de flecha es un buen ejemplo de tal caso (una matriz diagonal más una última fila y columna densas).
Jack Poulson
¿Es "patrón de dispersión" la palabra correcta aquí? que yo sepa, usted pregunta acerca de la ordenación de las entradas de la matriz, mientras que el término "patrón de escasez" se refiere a, por ejemplo, en diagonal, tridiagonales, diagonales por bloques, etc.
shuhalo
@ Martin Tenga en cuenta que una propiedad como "tridiagonal" todavía depende del orden. Piense en un problema 1D en el orden aleatorio, por ejemplo.
Jed Brown

Respuestas:

6

El pedido solo es significativo en el equilibrio de carga / comunicación y la idoneidad para el preacondicionamiento. El método de Krylov no se preocupa por el orden o incluso si las entradas de la matriz están almacenadas.

En la práctica, un mal pedido puede requerir mucha más comunicación de la necesaria cuando se multiplica por una matriz. Consulte la sección del Manual del usuario de PETSc sobre "Pedidos naturales" versus "Pedidos de PETSc" para ver un ejemplo. Además, un orden correspondiente a una partición paralela incorrecta podría hacer que los preacondicionadores de descomposición de dominio sean menos efectivos. Tenga en cuenta que es la partición lo que importa aquí, aunque una partición induce una ordenación (clase de equivalencia de).

Jed Brown
fuente