1
$\begingroup$

Examine a dynamic 2D heat equation $\dot{u} = \Delta u$ with zero boundary temperature. A standard finite difference approach is used on a rectangle using a $n\times n$ grid. For the resulting linear systems a banded Cholesky solver is used. Compare the three methods explicit, implicit and Crank-Nicolson for the time stepping.

  • Explicit method

$$ \begin{gathered} \frac{u_{i+1,j} - u_{i,j}}{\Delta t} = \kappa \frac{u_{i,j-1} - 2u_{i,j} + u_{i,j+1}}{(\Delta x)^2} \\ u_{i+1,j} = u_{i,j} + \frac{\kappa \Delta t}{(\Delta x)^2}(u_{i,j-1} - 2u_{i,j} + u_{i,j+1})\\ \vec{u}_{i+1} = \vec{u}_i - \kappa \Delta t \textbf{A}_n \cdot \vec{u}_{i}\\ \end{gathered} $$

  • Implicit method

$$ \begin{gathered} \frac{u_{i+1,j} - u_{i,j}}{\Delta t} = \kappa \frac{u_{i+1,j-1} - 2u_{i+1,j} + u_{i+1,j+1}}{(\Delta x)^2} \\ \vec{u}_{i+1} = \vec{u}_i - \kappa \Delta t \textbf{A}_n \cdot \vec{u}_{i+1}\\ u_i = (\mathbb{I}_n + \kappa \Delta t \textbf{A}_n)^{-i}\cdot \vec{u}_0 \end{gathered} $$

  • Crank-Nicolson

$$ \begin{gathered} \frac{u_{i+1, j}-u_{i,j}}{\kappa \Delta t} = \frac{u_{i,j-1} - 2u_{i,j} + u_{i,j + 1}}{2(\Delta x)^2} + \frac{u_{i+1,j-1} - 2u_{i+1,j} + u_{i+1,j + 1}}{2(\Delta x)^2}\\ \vec{u}_{i+1} - \vec{u}_i = -\frac{\kappa \Delta t}{2}(\textbf{A}_n \cdot \vec{u}_{i+1} + \textbf{A}_n \cdot \vec{u}_i) \end{gathered} $$

Here is the question:

Does the implicit method require the least memory?

Here is my proposition for an answer:

I would say that the statement if FALSE

The implicit method requires more computational effort to give an answer, because the matrix $\textbf{A}_n$ needs to be inverted. However, I would say that this is not the reason why the statement is false: for the implicit method there is $\textbf{no extra/less storage needed}$ (compared to the explicit method for example) because there is no extra data generated from the computation (for example no other matrix generated). Is the answer correct as well as the reasoning behind it?

Following the comments of @zimbra314, I posted the question in Computational science beta

$\endgroup$
  • $\begingroup$ The explicit methods should also be $u_i$ on the very right hand side of the bottom equation. then you can solve for $u_{i+1}$ explicitly. $\endgroup$ – tch Jan 3 at 16:02
  • 1
    $\begingroup$ I think your reasoning is right. All the methods require you to store a current iterate and the matrix. It is possible that solving a linear system will require some additional memory, but that wouldn't mean the implicit memory uses less. Also, everything you do in the implicit method you need to do in the Crank-Nicholson method anyway, so there is no reason the implicit method would use less memory that Crank-Nicholson. $\endgroup$ – tch Jan 3 at 16:06
  • $\begingroup$ Thanks for the comments @tch. I corrected the question according to your first comment. Regarding the second one, that's indeed the point which is not clear for me, but it seems we have the same intuition $\endgroup$ – ecjb Jan 3 at 16:11
  • $\begingroup$ this question might be better suited for scicomp.stackexchange.com $\endgroup$ – piyush_sao Jan 3 at 16:21
1
$\begingroup$

It depends on how do you apply inversion. If you use a direct method such as LU factorization, the inverted matrix will have more non-zero entries due to fill-in. For $n\times n$ 2D grid, $A$ matrix will have $\mathcal{O}(n^2)$ entries while factored matrix will have $\mathcal{O}(n^{2} \log n)$ entries; so it would require more memory than explicit method.

$\endgroup$
  • $\begingroup$ Thanks for the helpful comment @zimbra314. Then just to make the comparison straightforward. what would be the memory cost of explicit method in your example? $\endgroup$ – ecjb Jan 3 at 16:14
  • $\begingroup$ $O(n^{2})$ on $n\times n$ 2D grid $\endgroup$ – piyush_sao Jan 3 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.