Estoy resolviendo el sistema de reacción-difusión de Turing con el siguiente código C ++. Es demasiado lento: para una textura de 128x128 píxeles, el número aceptable de iteraciones es 200, lo que resulta en 2.5 segundos de retraso. Necesito 400 iteraciones para obtener una imagen interesante, pero 5 segundos de espera es demasiado. Además, el tamaño de la textura debería ser de hecho 512x512, pero esto da como resultado un gran tiempo de espera. Los dispositivos son iPad, iPod.
¿Hay alguna posibilidad de hacer esto más rápido? El método de Euler converge lentamente (wikipedia). ¿Tener un método más rápido permitiría eliminar varias iteraciones?
EDITAR: Como señaló Thomas Klimpel, las líneas: "if (m_An [i] [j] <0.0) {...}", "if (m_Bn [i] [j] <0.0) {...}" están retrasando la convergencia: después de eliminar, aparece una imagen significativa después de 75 iteraciones . He comentado las líneas en el código a continuación.
void TuringSystem::solve( int iterations, double CA, double CB ) {
m_iterations = iterations;
m_CA = CA;
m_CB = CB;
solveProcess();
}
void set_torus( int & x_plus1, int & x_minus1, int x, int size ) {
// Wrap "edges"
x_plus1 = x+1;
x_minus1 = x-1;
if( x == size - 1 ) { x_plus1 = 0; }
if( x == 0 ) { x_minus1 = size - 1; }
}
void TuringSystem::solveProcess() {
int n, i, j, i_add1, i_sub1, j_add1, j_sub1;
double DiA, ReA, DiB, ReB;
// uses Euler's method to solve the diff eqns
for( n=0; n < m_iterations; ++n ) {
for( i=0; i < m_height; ++i ) {
set_torus(i_add1, i_sub1, i, m_height);
for( j=0; j < m_width; ++j ) {
set_torus(j_add1, j_sub1, j, m_width);
// Component A
DiA = m_CA * ( m_Ao[i_add1][j] - 2.0 * m_Ao[i][j] + m_Ao[i_sub1][j] + m_Ao[i][j_add1] - 2.0 * m_Ao[i][j] + m_Ao[i][j_sub1] );
ReA = m_Ao[i][j] * m_Bo[i][j] - m_Ao[i][j] - 12.0;
m_An[i][j] = m_Ao[i][j] + 0.01 * (ReA + DiA);
// if( m_An[i][j] < 0.0 ) { m_An[i][j] = 0.0; }
// Component B
DiB = m_CB * ( m_Bo[i_add1][j] - 2.0 * m_Bo[i][j] + m_Bo[i_sub1][j] + m_Bo[i][j_add1] - 2.0 * m_Bo[i][j] + m_Bo[i][j_sub1] );
ReB = 16.0 - m_Ao[i][j] * m_Bo[i][j];
m_Bn[i][j] = m_Bo[i][j] + 0.01 * (ReB + DiB);
// if( m_Bn[i][j] < 0.0 ) { m_Bn[i][j]=0.0; }
}
}
// Swap Ao for An, Bo for Bn
swapBuffers();
}
}
Respuestas:
Parece estar limitado por la estabilidad, que se espera ya que la difusión es rígida a medida que refina la cuadrícula. Los buenos métodos para sistemas rígidos son al menos parcialmente implícitos. Tomará un poco de esfuerzo, pero puede implementar un algoritmo simple de múltiples cuadrículas (o usar una biblioteca) para resolver este sistema con un costo de menos de diez "unidades de trabajo" (esencialmente el costo de uno de sus pasos de tiempo). Cuando refina la cuadrícula, el número de iteraciones no aumentará.
fuente
Desde un punto de vista práctico: el procesador A5 no es tan potente, por lo que puede esperar algunas iteraciones de HW, o si su ipod / ipad va a estar conectado a Internet, resuelva su problema de forma remota o en la nube.
fuente
Euler converge lentamente en relación con otros métodos, sin embargo, no creo que eso sea lo que le interesa. Si solo está buscando imágenes "interesantes", aumente el tamaño de su paso de tiempo y tome menos iteraciones. El problema, como señala Jed, es que el método euler explícito tiene problemas de estabilidad con grandes pasos de tiempo en relación con el tamaño de la cuadrícula. cuanto más pequeña sea su cuadrícula (es decir, cuanto mayor sea la resolución de su imagen), más pequeño debe ser su paso de tiempo para tenerla en cuenta.
Por ejemplo, al usar euler implícito en lugar de explícito, no obtienes ningún orden de convergencia, pero la solución tendrá una estabilidad incondicional, permitiendo pasos de tiempo mucho más largos. Los métodos implícitos son más complicados de implementar y requieren más cómputo por paso de tiempo, pero debería ver ganancias mucho más allá de eso al tomar menos pasos en total.
fuente