Método Euler explícito muito lento para problemas de difusão de reação

10

Estou resolvendo o sistema de reação-difusão de Turing com o seguinte código C ++. É muito lento: para a textura de 128x128 pixels, o número aceitável de iterações é 200 - o que resulta em 2,5 segundos de atraso. Preciso de 400 iterações para obter uma imagem interessante - mas 5 segundos de espera são demais. Além disso, o tamanho da textura deve ser de 512x512 - mas isso resulta em um grande tempo de espera. Os dispositivos são iPad, iPod.

Existe alguma chance de fazer isso mais rápido? O método de Euler converge lentamente (wikipedia) - ter um método mais rápido permitiria eliminar o número de iterações?

Edição: Como Thomas Klimpel apontou, as linhas: "if (m_An [i] [j] <0.0) {...}", "if (m_Bn [i] [j] <0.0) {...}" estão atrasando a convergência: após a remoção, uma imagem significativa aparece após 75 iterações . Eu comentei as linhas no código abaixo.

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();
    }
}
AllCoder
fonte
Além disso, quero mencionar que é preferível que você não faça perguntas cruzadas, pois parece que você fez perguntas muito semelhantes aqui e aqui .
Godric Seer
Você já viu o trabalho de Greg Turk nisso, por acaso?
JM
@JM: Ainda não. Eu apenas tentei executar o código dele: ele requer um servidor X com PseudoColor, ou seja, profundidade de cores de 8 bits. Eu acho que não posso fornecer isso no OSX. Eu tentei vários servidores VNC, mas sem sorte.
AllCoder
Eu acho que você ainda deve ser capaz de adaptar a abordagem de Turk ao assunto em questão; os padrões de difusão de reação parecem ser usados ​​bastante nos gráficos de computador atualmente.
22412 JM
11
Eu posso estar errado, mas a parte com m_An [i] [j] = 0.0; pode realmente adicionar um elemento a esse sistema que não pode ser modelado por uma equação diferencial com um lado direito contínuo. Isso torna um pouco difícil encontrar um solucionador mais rápido.
22612 Thomas Klimpel

Respostas:

9

Você parece estar limitado pela estabilidade, o que é esperado, já que a difusão é rígida à medida que você refina a grade. Bons métodos para sistemas rígidos são pelo menos parcialmente implícitos. Isso exigirá algum esforço, mas você pode implementar um algoritmo multigrid simples (ou usar uma biblioteca) para resolver esse sistema com um custo inferior a dez "unidades de trabalho" (essencialmente o custo de uma de suas etapas de tempo). Quando você refina a grade, o número de iterações não aumenta.

Jed Brown
fonte
Se apenas a difusão fosse rígida aqui, ele poderia usar um método ADI como Douglas-Gunn e tudo ficaria bem. No entanto, na minha própria experiência, a parte da reação geralmente é muito pior com relação à rigidez, além de ser muito não-linear.
22612 Thomas Klimpel
11
Infelizmente, a ADI possui uma terrível localidade de memória. Observe também que a reação pode ser tratada implicitamente, independentemente da difusão. Sob o refinamento da grade, a difusão acabará se tornando dominante, mas não podemos dizer onde está o limite sem conhecer as constantes.
22712 Jed Brown
Código de exemplo a implementação trás Euler para esta (em Python) é aqui: scicomp.stackexchange.com/a/2247/123
David Ketcheson
@ DavidKetcheson: O uso de métodos implícitos requer a solução de uma equação? É por isso que existe linalg.spsolve () no código?
AllCoder
11
@AllCoder Sim, requer uma solução, mas a solução pode ser feita muito mais rapidamente do que as etapas necessárias para que um método explícito seja estável.
22712 Jed Brown
2

Do ponto de vista prático: o processador A5 não é tão poderoso, então você pode esperar algumas iterações de HW ou, se o seu ipod / ipad for conectado à Internet, resolver seu problema remotamente ou na nuvem.

fcruz
fonte
Estou surpreso com a pequena potência que o A5 oferece. Como o Pages, Safari e outros aplicativos grandes funcionam tão bem? Eu preciso gerar imagens aleatórias, abstratas, pensou que a morfogênese será suficiente simples ..
AllCoder
Bem, o A5 é um processador energeticamente eficiente, otimizado para web e vídeo (Pages, Safari, etc.). Por outro lado, a maioria das cargas de trabalho numéricas realiza toneladas de operações de ponto flutuante e movimentação de dados, esses recursos não são o foco de processadores móveis de baixa potência.
22712 fcruz
0

Euler converge lentamente em relação a outros métodos, no entanto, acho que não é isso que você está interessado. Se você está apenas procurando imagens "interessantes", aumente o tamanho do seu passo de tempo e faça menos iterações. O problema, como Jed aponta, é que o método euler explícito apresenta problemas de estabilidade com grandes etapas de tempo em relação ao tamanho da grade. quanto menor for sua grade (ou seja, quanto maior a resolução da sua imagem), menor será o tempo necessário para explicá-la.

Por exemplo, usando o euler implícito em vez do explícito, você não obtém nenhuma ordem de convergência, mas a solução terá estabilidade incondicional, permitindo etapas de tempo muito maiores. Os métodos implícitos são mais complicados de implementar e exigem mais computação por etapa de tempo, mas você deve ver ganhos muito além disso executando menos etapas no total.

Godric Seer
fonte
Esse problema é limitado pela estabilidade; portanto, simplesmente aumentar o tamanho da etapa de tempo não funcionará.
Jed Brown
Se eu mudar de 0,01 para, por exemplo, 0,015, recebo "concentração da química. Sp. Perto de zero" em todos os pontos - ou seja, um quadrado cinza. Aqui está a origem do meu código: drdobbs.com/article/print?articleId=184410024
AllCoder
Sim, isso seria resultado dos problemas de estabilidade mencionados por Jed. Como ele menciona em sua resposta, o uso de um método implícito caracterizado por melhor desempenho de estabilidade resolverá esse problema para você. Vou atualizar minha resposta para remover as informações irrelevantes.
Godric Seer