Skip to main content
Share Your Experience: Take the 2024 Developer Survey
43 votes

Good examples of "two is easy, three is hard" in computational sciences

One example that appears in many areas of physics, and in particular classical mechanics and quantum physics, is the two-body problem. The two-body problem here means the task of calculating the ...
davidhigh's user avatar
  • 3,127
37 votes

Good examples of "two is easy, three is hard" in computational sciences

In one and two dimensions, all roads lead to Rome, but not in three dimensions. Specifically, given a random walk (equally likely to move in any direction) on the integers in one or two dimensions, ...
Mark L. Stone's user avatar
32 votes

Good examples of "two is easy, three is hard" in computational sciences

A famous example is the boolean satisfiability problem (SAT). 2-SAT is not complicated to solve in polynomial time, but 3-SAT is NP-complete.
Federico Poloni's user avatar
29 votes

Good examples of "two is easy, three is hard" in computational sciences

In social choice theory, designing an election scheme with two candidates is easy (majority rules), but designing an election scheme with three or more candidates necessarily involves making trade-...
ajd's user avatar
  • 391
29 votes
Accepted

Conserving Energy in Physics Simulation with imperfect Numerical Solver

There are a few ways to conserve energy during ODE integration. Method 1: Symplectic Integration The cheapest way that is to use a symplectic integrator. A symplectic integrator solves the ODE on a ...
Chris Rackauckas's user avatar
27 votes

Good examples of "two is easy, three is hard" in computational sciences

Here's one close to the hearts of the contributors at SciComp.SE: The Navier–Stokes existence and smoothness problem The three-dimensional version is of course a famous open problem and the subject ...
Richard Zhang's user avatar
24 votes

What language should I use when teaching an undergraduate course in computer programming?

In 2014, I would've said Python. In 2017, I wholeheartedly believe that the language to teach undergraduates is Julia. Teaching is always about a tradeoff. On one hand, you want to choose something ...
Chris Rackauckas's user avatar
16 votes

Good examples of "two is easy, three is hard" in computational sciences

Simultaneous diagonalization of two matrices $A_1$ and $A_2$: $$ U_1^T A_1 V = \Sigma_1,\quad U_2^TA_2V=\Sigma_2 $$ is covered by existing generalized singular value decomposition. However, when the ...
Anton Menshov's user avatar
  • 8,672
15 votes
Accepted

Why is leapfrog integration symplectic and RK4 not, if the latter is more accurate?

TL;DR: It depends on what kind of accuracy you need. Energy conservation does not automatically equal accuracy. Suppose, you want to simulate the solar system, and you are using a solver that – to ...
Wrzlprmft's user avatar
  • 2,022
15 votes

Time and memory required to diagonalize a 18000 by 18000 matrix using numpy in python

A 20000 by 20000 double-precision complex matrix requires $20000 \times 20000 \times 8 \times 2=6.4 \mbox{gigabytes}$ of RAM. The LAPACK routines ZHEEV that will do the work for you will store the ...
Brian Borchers's user avatar
14 votes
Accepted

Galerkin method: Test functions vs. Basis functions

Suppose that the solution $u$ of the PDE lives in some function space $X$. We'll write the PDE as a bilinear form $A(u, v) = f(v)$ for all $v$ in $X$, where $f$ is some element of the dual space $X^*...
Daniel Shapero's user avatar
13 votes

Why is it not computationally possible to accurately predict the weather that would occur after 14 days?

Further to Chris' answer: Yes, weather (or the equations describing it) is extremely sensitive to the initial conditions. The fact that the weather system contains phenomena at pretty much all time ...
GoHokies's user avatar
  • 2,216
12 votes

Finite-difference software for solving custom equations

I'm going to assume since you mention electrodynamics that you're interested in PDEs. You've already mentioned FEniCS in your comment. FEniCS offers a domain-specific language (DSL) called UFL. This ...
Daniel Shapero's user avatar
10 votes

Good examples of "two is easy, three is hard" in computational sciences

There are plenty of examples in quantum computing, although I've been out of this for a while and so don't remember many. One major one is that bipartite entanglement (entanglement between two ...
Dan Stahlke's user avatar
10 votes
Accepted

Euler integration of the three-body problem

What you see is a result of Euler integration. One thing you can do is change to a symplectic integration which does not add energy to the system. You can quickly try this out, but moving the update ...
John Alexiou's user avatar
9 votes

Why is it not computationally possible to accurately predict the weather that would occur after 14 days?

Errors grow exponentially in a chaotic system, and most people believe weather is chaotic. So even if you get a fairly exact numerical approximation, the fact that your input data (temperatures, etc.) ...
Chris Rackauckas's user avatar
9 votes
Accepted

Consumer hardware for scientific computing?

One issue that you should be aware of is that NVIDIA has a market segmentation strategy in which it sells relatively inexpensive GPU's to the gaming and graphics workstation markets (GeForce and ...
Brian Borchers's user avatar
8 votes

In Matlab, how can I be consistent with units?

Just simply by being consistent in all of my code? Yes this is the only way. Matlab or any other programming language does not know about units. They only know about numbers. As an example consider ...
cfdlab's user avatar
  • 3,028
8 votes
Accepted

In Matlab, how can I be consistent with units?

I would say that you have, mainly, two methods: Being consistent in all your code, as already suggested in another answer. For that purpose, I always keep a table like this one with me, since it ...
nicoguaro's user avatar
  • 8,515
8 votes

Why there are people that still prefer fortran 77 over new versions?

I think it's generally true that there are no advantages of Fortran 77 over either newer versions of Fortran or in fact any number of other programming languages that are widely used in scientific ...
Wolfgang Bangerth's user avatar
8 votes

Good examples of "two is easy, three is hard" in computational sciences

A smooth curve of degree 2 (i.e. given as the solution of $f(x,y) = 0$ where $f$ is a polynomial of degree 2) with a given point is rational, meaning that it can be parameterized by quotients of ...
doetoe's user avatar
  • 593
8 votes

Good examples of "two is easy, three is hard" in computational sciences

Here's a neat one from optimization: the Alternating Direction Method of Multipliers (ADMM) algorithm. Given an uncoupled and convex objective function of two variables (the variables themselves ...
Nathaniel Kroeger's user avatar
8 votes

Finite-difference software for solving custom equations

You might want to check out DifferentialEquations.jl. It supports ODEs, PDEs, stochastic equations, delay equations, and basically everything else. It also has really good automatic sparsity detection ...
Oscar Smith's user avatar
8 votes
Accepted

Why are fluid simulations so hard?

At their core, simulation of realistic fluid behavior is difficult because of the length scales involved. If you have turbulent flow, as is common in hydrodynamic or magneto-hydrodynamic situations, ...
Wolfgang Bangerth's user avatar
7 votes

How can an engineering student become a computational scinece expert in a short time

There is no shortcut. Just like there is no shortcut to becoming an "engineering expert in a short time". The thing is that to be an expert in civil engineering, you need to understand load analysis, ...
Wolfgang Bangerth's user avatar
7 votes

Calculating partial trace of array in NumPy

I didn't follow exactly your notation so I can't say for sure what this would look like for your example, but two suggestions: if you really want your life made simple, check out ...
Okarin's user avatar
  • 191
7 votes

Physics Simulation in C++

I think you are missing a very important and crucial step that lies exactly between the physics and simulation: the mathematical model. In order to model any physics, one has to formulate the ...
Anton Menshov's user avatar
  • 8,672
7 votes

Efficiently finding all (x,y,z) points within certain distance of point P

You can use Morton keying to sort the coordinate locations by binning them into cubes of some specified size $d$. This is an $\mathcal{O}(N\log N)$ operation. Then, given any point P, you can use its ...
coolguy1000000's user avatar
7 votes

Good examples of "two is easy, three is hard" in computational sciences

Angle bisection with straightedge and compass is simple, angle trisection is in general impossible.
davidhigh's user avatar
  • 3,127

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