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 ...
- 2,982
36
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, ...
- 2,077
31
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.
- 10.1k
28
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-...
- 381
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 ...
- 2,435
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 ...
- 8,572
11
votes
Accepted
How important is learning hardware/architecture for scientific computing?
I haven't worked in quantum chemistry specifically, but I've worked in other areas where high performance is a correctness requirement (along with scientific accuracy), so I think we're on the same ...
- 351
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 ...
- 209
9
votes
Accepted
Computer Build for Scientific Computing
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 ...
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 ...
- 583
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 ...
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.
- 2,982
7
votes
Accepted
Choice between DAE or ODE formulation for chemical systems
The trade-off is generally this:
ODEs are numerically a lot of easier to solve than DAEs, in particular if the algebraic constraint is nonlinear (yours is linear). So that argues for the ODE ...
6
votes
Borrow computational power from machines around me
You could install BOINC on those machines. When the computers become idle, the BOINC screensaver/client requests tasks from a server and computes them. See more information about it here. This is ...
- 3,994
6
votes
What determines the usual chemistry textbook plots of atom orbitals?
Your intuition is right, for example in 3D Orbitals (German Wikipedia) the caption explicitly states that 90% iso-surfaces are used. I have however seen different percentages before where the results ...
- 156
5
votes
Accepted
Borrow computational power from machines around me
You can use HTCondor that is designed exactly to "steal" cpu cycles from remote machines. It may be a little difficult to setup but I think this may be the best approach.
- 166
5
votes
Good examples of "two is easy, three is hard" in computational sciences
Type inference for Rank-n types. Type inference for Rank-2 is not especially difficult, but type inference for Rank-3 or above is undecidable.
5
votes
Accepted
What equation should I fit this set of data points to?
You could either fit a logistic function (possibly composing it with a linear function), use segmented regression, or classification and regression trees, among other options.
The original data, ...
- 3,994
5
votes
Good examples of "two is easy, three is hard" in computational sciences
The problem on which I originally made that comment is a linear algebra problem: consider the linear matrix equation
$$
\sum_{i=1}^k A_i X B_i = C,
$$
where $A_i,B_i,C \in \mathbb{R}^{n\times n}$ are ...
- 10.1k
5
votes
Accepted
Maximize a function of an orthogonal matrix
There are specialized methods for the minimization of a differentiable function $f(X)$ subject to the orthogonality constraint $X^{T}X=I$. See for example:
Lai, Rongjie, and Stanley Osher. “A ...
- 18.2k
4
votes
How does one determine the point group of a molecule?
I'm happy to answer that there's a high-quality open source code for this:
https://github.com/mcodev31/libmsym
libmsym is a C library dealing with point group symmetry in molecules. It can ...
- 141
4
votes
What are the things I should keep in mind before doing an analysis of my gromacs simulation?
I think that this question is too generic for a complete answer, as the latter would depend entirely on what you are simulating and what observables you are interested in.
The only things that come to ...
- 677
4
votes
Good examples of "two is easy, three is hard" in computational sciences
The infinite square well potential problem in non-relativistic quantum mechanics has energy eigenvalues $E_n=n^2\hbar^2\pi^2/2mL^2$,where $n^2=\sum_{k=1}^Nn_k^2$($N$=number of dimensions).
A problem ...
- 223
4
votes
Good examples of "two is easy, three is hard" in computational sciences
In discretized PDEs you find very sparse matrices: even with a matrix size of billions, the number of nonzeros per row is O(1). Doing Gaussian elimination on such a matrix destroys that sparsity: a ...
- 1,305
4
votes
Accepted
Getting started with Computational Chemistry
Computational chemistry is a broad field, even more nowadays with increasing number of machine learning applications related to chemistry. As you have not specified what you are after I will suppose ...
- 56
4
votes
Applications of Julia in Chemistry and Molecular Physics?
It's an entire programming language with a large community, so it's pretty much impossible to dig up all examples of its usage in these fields, but I can point to a few resources to get you started. ...
- 12.1k
4
votes
How important is learning hardware/architecture for scientific computing?
I want to support the response from @Pseudonym, who makes the point that not everyone in the team needs to contribute to every aspect of the project. Something related to consider is that you are ...
- 994
4
votes
Accepted
Quasi-Newton Method with a Transformed Hessian
It might help us give a better answer if you give more details of your problem.
But I think what's going on is effectively elimination of equality constraints.
I'll take just translation as an example....
- 9,168
4
votes
Does it make any sense to acquire some sort of knowledge about manufacturing or engineering for computational design optimization?
Computation science lives by the grace of computing something. So if you learn about that something you will 1. make yourself more employable as an engineer, specializing in computational stuff, or 2. ...
- 1,305
3
votes
Good examples of "two is easy, three is hard" in computational sciences
Folding a piece of paper in half without tools is easy. Folding it into thirds is hard.
Factoring a polynomial with two roots is easy. Factoring a polynomial with three roots is significantly more ...
- 131
Only top scored, non community-wiki answers of a minimum length are eligible