11

I would not insist on demanding a geometrical meaning from Galerkin methods in general. There is a connection, but it becomes less meaningful as you extend it further and further. (In a sense, it would be better to call Galerkin methods "generalized projection methods".) To really understand the connection between collocation and Galerkin methods requires ...


10

The reason is that with the exception of linear problems, if you do a Fourier (or other) decomposition in time, you end up with a significant number of problems that are coupled globally in time. In other words, you have to solve lots of problems on the entire time interval concurrently. That will typically bust your computational or memory budget. The ...


9

Just as an aside, your github documentation is fantastic. This is just a guess from DG methods, which can have similar issues if numerical fluxes aren't chosen carefully (I figure FV methods are a subset of DG methods). If you're using interpolation from cell centers to define your fluxes, then this should be equivalent to using the average as a numerical ...


8

Many of us in scientific computing simply have well-equipped laptops for regular software development tasks, some multicore workstations for smaller-scale testing, and access to clusters for larger runs. To give you an idea: My laptop is a Dell M3800 (4-core Intel i7, hyperthreading, 16GB of RAM). This is good enough to regularly compile my software and do ...


7

We have the following problem: $$\frac{\partial u}{\partial t}+v\color{red}{\frac{\partial u}{\partial x}}-\nu\color{blue}{\frac{\partial^2u}{\partial x^2}}=0 \tag{*}$$ The function $u$ may represent for example the concentration that propagates at velocity $v>0$ and disperses in a medium with viscosity $\nu>0$. Since only we are discussing how terms ...


7

Instead of directly integrating over the area, it is often more convenient to use the divergence theorem to replace the area integral with an integral over the boundary edges. The divergence theorem in three dimensions for a vector function $F$ can be written $$ \int_V \nabla \cdot {\bf F} dv = \int_S {\bf F} \cdot ds $$ That is, an integral over the ...


6

Every major class of discretization is "open-ended" in the sense that there are decisions with no obviously/provably correct answer in the general case, so some decisions are made based on how they perform for the target problem. Additionally, each major class has active research on new extensions. AMR has more choices than static-grid discretizations, so ...


6

Full space-time discretization of time-dependent partial differential equations is indeed a thing. If you use a structured mesh in time (in the sense that the time discretization does not depend on space) and appropriate choice of trial and test functions, you can fit several standard time-stepping methods (Crank-Nicolson, implicit Euler or some Runge-Kutta ...


6

I believe the best approach here is to use a threshold based on the local average brightness of the image. Setting the threshold to be 90% of the mean value of the 11x11 grid surrounding each pixel gives results that are about as good as you can expect with such a low resolution image. For each pixel you just need to compute the mean brightness of the ...


6

There is a difference between the requirements for a hyperbolic pde like $$ u_t + a u_x = 0 $$ and for a purely parabolic pde like $$ u_t = u_{xx} $$ Suppose the solutions are smooth and you approximate them by some finite difference method. Then in case of hyperbolic problem, the maximum error in the numerical solution depends on the time interval of ...


5

For the particular equation you are solving (called the minimal surface equation), the functional you are trying to minimize is $$ J(u) = \int_\Omega \sqrt{1 + |\nabla u|^2} \; dx. $$ You can find a derivation of the equations, as well as a discussion of solution approaches in lectures 31.5 and following here: http://www.math.tamu.edu/~bangerth/videos....


5

If you wish to know only the change in density you are interested in the dilatation or volumetric strain of the stress tensor associated with the transformation. If you also wish to know about the anisotropy of the stretching you should look at computing the right Cauchy-Green deformation tensor, $\Delta$, and it's associated eigenvalues and eigenvectors. ...


5

Section 2.5 of this PDF document goes through some additional details and the error does in fact work out to be second order. The key is that the term multiplying the $\Delta y^2/\Delta x$ term is equal to $$\Delta x\left( \dfrac{\partial^4u}{\partial x\partial y^3} +\mathcal{O}(\Delta x^2) \right)$$ The $1/\Delta x$ cancels the $\Delta x$ in this term ...


5

Adaptive refinement. There are even optimal error estimators for your exact problem, though you can't go too wrong on this problem by dividing cells where the magnitude of the gradient is largest.


5

The concept of $p$-nonconforming meshes can also apply to continuous FEM, not just DG. For continuous FEM, continuity is enforced by enforcing a single set of degrees of freedom on a face shared between two elements. If those elements have varying polynomial degrees, the trace space on the face must be made the same. This may be done by restricting the ...


5

You can't. Nonlinear systems of equations are in general not solvable exactly. What you need to do is to use a method to solve nonlinear systems, of which there are of course quite a lot: A simple approach would be to use $D(U)\approx D(U^{n-1})$, where $D^{n-1}$ is the solution of the previous time step. A possibly smarter approach would be to use $D(U)\...


4

Previous comments gave you good suggestions, I try to add some more. Firstly, your example 2x2 really does not correspond to zero Neumann boundary conditions. In fact, one can show that your choice leads to zero Dirichlet boundary conditions. If you domain is a rectangle, then implementing the zero Neumann condition can be done easily. You have to include ...


4

It is quite straightforward to demonstrate this for implicit Euler (aka backward Euler) on a scalar example. Consider the initial value problem $\dot{y}(t) = i \alpha y(t), \ y(0) = 1$ with solution $y(t) = \exp(i \alpha t) = \cos(\alpha t) + i \sin(\alpha t)$. The solution is a harmonic oscillation with amplitude 1 and this amplitude does not change ...


4

Since you are a computer science major, let me posit the following analogy: "adaptive mesh refinement" is a set of techniques for solving partial differential equations in mathematics; this is in the same spirit as "image processing" is a set of techniques to transform and improve images. Both fields have many different aspects, so there are no fixed ...


4

The expressions you are using for eigenvalues and eigenfunctions are wrong (as per Wolfgang Bangerth's comment); therefore the results you are getting are not meaningful at all. There are analytic expressions for eigenvalues for both continuous and discrete cases for $d^2/dx^2$ on a circular segment – periodic BCs. For a continuous case on $S^1=[0,L]$, $j$...


4

For something with a spectral flavor in time, look at deferred correction methods, starting with this paper. I would argue that they're not spectral in the usual sense of the word, but they give you a family of arbitrary-order Runge-Kutta methods, so if you think of "refining" by increasing the order (by adding more nodes), then the convergence can be ...


4

Central differencing schemes are not stable if you have advection dominated problems. There really was no other trivial [1] alternative to developing upwind schemes. [1] There are a few other stabilization methods, of course, but in the finite difference of finite volume context, almost everything that was developed over the first 30 years of numerical ...


4

To elaborate on Wolfgang's answer: since hyperbolic PDE semi-discretizations with centered differences have purely imaginary eigenvalues, they are only neutrally stable. For linear problems (e.g., the acoustic wave equation or linear Maxwell's equations) this is fine and such methods are commonly used. For instance, in electromagnetics centered differences ...


4

Basically, you have the following set of derivations: Strong form of the PDE -> Finite differences Integral form of the PDE -> Finite volumes Weak (variational) form of the PDE -> Galerkin methods (including FEM and DGFEM)


4

Short answer: yes (in exact arithmetic). You'll have to use the centered difference formula evaluated at $x \pm \frac{1}{2}\delta x$, like this: $$ u_x = \frac{u(x + \frac{1}{2}\delta x) - u(x - \frac{1}{2}\delta x)}{\delta x} + {\cal O}(\delta x^2) $$ Then, applying the formula recursively, you arrive at the "standard" second order finite-difference ...


4

For the discontinuous Galerkin method, the choice of control points is entirely unimportant because they conceptually lie in the interior of the cell (even if they are physically on the boundary of the cell). We think of a control point that is conceptually located at a vertex to be one that all cells adjacent to that vertex share; and of one on an edge that ...


4

There are actually a few different 9 point stencils in use, but they can all be written as a linear combination of the standard and skewed 5 point stencils. Performing the usual von Neumann analysis for a general Fourier mode, $e^{ikx+ily}$, produces an equation like $$a_{n+1} = a_n \left(1-\lambda+\frac{\alpha\lambda}{2}\left[\cos\theta_1+\cos\theta_2\right]...


4

When dealing with conservation laws like your case, you can often make use of the divergence theorem (as you did). You can then express the fact that the total mass within your integration region is preserved by the following surface integral: $$\oint_{\partial \Omega} k \nabla T \cdot \mathbf{n} ~\partial S = 0$$ Now, as it stands, it is irrelevant which ...


4

After doing some quick research, I am convinced that the interviewer was looking for an answer related to one of the data trees. Depending on the application, one might be better than the others, but all of them are suitable for this general description. mat[i][j] might be available on a hard disk -which are capable of storing 16TBs of data nowadays- but may ...


3

I think that from a practical perspective, it's not an important point. Sure, you have less data to send around, and to fewer neighbors, but I don't think I've ever seen anyone quantify the impact in any meaningful way. Papers about DG tend to repeat the same arguments in favor of DG methods over and over without attribution to a source and without ...


Only top voted, non community-wiki answers of a minimum length are eligible