Reducción cíclica

La reducción cíclica es un método numérico para resolver grandes sistemas lineales mediante la división repetida del problema. En cada paso se eliminan filas y columnas pares o impares de una matriz, manteniendo una forma similar. El paso de eliminación es relativamente costoso, pero la división del problema permite el cálculo en paralelo.

Este método solo se aplica a matrices que pueden representarse como una matriz de Toeplitz (por bloques) . Este tipo de problemas suelen surgir en soluciones implícitas de ecuaciones diferenciales parciales en una red. Por ejemplo, los solucionadores rápidos de la ecuación de Poisson plantean el problema como la resolución de una matriz tridiagonal, discretizando la solución en una malla regular.

Los sistemas que inicialmente tienen buena estabilidad numérica tienden a mejorar con cada paso. Además, hasta un punto en el que se puede dar una buena solución aproximada, ^{[ 1 ]} pero debido a que se debe preservar la forma especial de la matriz, no se puede realizar el pivoteo para mejorar la precisión numérica.

El método no es iterativo, sino que busca una solución exacta al problema lineal consistente con los valores límite dados, a diferencia del método multigrid, similar pero computacionalmente más económico , que propaga las estimaciones de corrección de errores y permite diferentes parámetros de relajación en diferentes escalas, cuyo aspecto iterativo permite una mejor incorporación de características no lineales.

La transformación desde el dominio espacial y la reformulación de la EDP se denomina método espectral ; el análisis de Fourier y la reducción cíclica se combinan en el algoritmo FACR ^{[ 2 ]} , que se explica en Recetas Numéricas (véase 19.4 Métodos de Fourier y Reducción Cíclica para Problemas de Valores en la Frontera) ^{[ 3 ] .}