KWrite

This is the continuation of my series “Bibles” in Applied Math. I write a new page for this section because it is a bit off from what most people call “Applied Math”. Further, this topic deserves a blog entry, or even a forum, on its own because being able to make your code run 10-15% faster (or even 90% faster if you haven’t mastered certain level of the art of programming) is a big deal nowadays. It can even land you a lucrative job (here’s an example).

Suppose that you’re a master of Numerical Algorithms. You’ve spent 2 years working on a complex engineering problem and recently have developed a new algorithm that can solve the problem in linear time instead of the state-of-the-art . Your new solver (and the 2 years) would be wasted if it is poorly written and/or poorly compiled. Here are a couple out of thousands of common poor programming practices.

1. Computing the same thing over and over again

for (int k=0;k<100;k++) {
 out[k] = 0;
 for (int i=0;i<M;i++)
  for (int j=0;j<N;j++)
   out[k] += kernel(i,j) * in[k];
}

In this example, kernel(i,j) is re-computed 99 times. Because this matrix Kernel is independent from the outer loop, it can and most of the times should be pre-computed. If the computation of kernel is computationally intensive, which is common, pre-computation of the matrix can make your program run 99.9 times faster.

2. Using the right flags when compiling

[zer0ne@ion]$ g++ myProgram.cpp -o myProgram
[zer0ne@ion]$ ./myProgram
Total time: 68.74 seconds
[zer0ne@ion]$ g++ -O3 myProgram.cpp -o myProgram
[zer0ne@ion]$ ./myProgram
Total time: 13.9 seconds
[zer0ne@ion]$ g++ -O3 -DNDEBUG myProgram.cpp -o myProgram
[zer0ne@ion]$ ./myProgram
Total time: 11.54 seconds

So, if you’re already good at designing algorithms, it’s worth to learn a bit of performance optimization tricks. I am no expert in HPC, let alone related fields such as Computer Architectures or Compilers, so my best bet is to point you to some great books out there. Also for the same reason, I’ll appreciate if you share your own tips.

1. Performance Optimization of Numerically Intensive Codes by Hoisie. $73 seems high for a 173-page book but this thin bible is worth every penny. It covers all basic stuffs such as CPU architecture, compiler optimization, memory localit, profiling, etc.
2. High Performance Computing by Kevin Dowd & Charles Severance. Similar contents but this book explains things in greater depth.

Awhile ago, I and other VNQF members posted some of the most famous books in Quantitative Finance and related fields (including Partial Differential Equations, Numerical Methods, Optimization, Parallel Computing). Recently, I’ve posted a few classic books in Applied Math, based on the request of a member in the VEF’s VietnamBookDrive project. Even more recently, anh Ngo Quang Hung (and “đồng bọn”) have created a list of great textbooks in Computer Science.

Here, I merely recompose the list of some bible books in Applied Math that I already did, but maybe more in depth and not limited to the scope of VEF. By Applied Math, I mean a wide spectrum from extremely mathematical topics (they’re essentially subsets of “Pure Math”) such as Partial Differential Equations to Computations (Numerical Analysis, Multiscale Modeling,…) to Probabilistic/Statistical Sciences to Computer Science and to a wide range of Applications (Physics, Chemistry, Biology, Engineering, Finance, Economics, Business, Medicines, etc.). Due to the breath and depth of this giant discipline, the list is by no mean complete and will be updated here continuously (possibly until I die).

For some of the books here, I have gone through or half-through or quarter-through. For the rest I haven’t but this doesn’t prevent them from being invaluable sources of reference. Another important note: the words in my description shouldn’t be quantified or taken superficially. For example: if I say something basic, it doesn’t necessarily mean easy stuff (well, may be for researchers in the field) and can be far beyond my understanding.

Read the rest of this entry »

• An execuse for not doing math homework: “I could only get arbitrarily close to my textbook, I couldn’t reach it.”
• Q: What is a topologist?
  A: Someone who cannot distinguish between a donut and a coffee cup.
• Q: What’s a dilemma?
  A: A lemma that produces two results.
• A mathematician and an engineer are on a desert island. They find two palm trees with one coconut each. The engineer shinnies up one tree, gets the coconut, and eats it. The mathematician hinnies up the other tree, gets the coconut, climbs the other tree and puts it here. “Now we’ve reduced it to a problem we know how to solve.”

Source

[from www.vnqf.org]

1. Let be a Brownian motion. What is ?
2. How do you compute
3. After each second, an insect may: either die, or survive, or split into 2, or split into 3 (each with probability 0.25). Suppose that there’s 1 insect at the beginning of the day, what is the probability that the whole population dies at the end of the day?
4. (Programming) Given 2 variables a and b. How do you swap the values of a and b without using any extra memory?
5. (Blog KHMT) Suppose (infinite power). What is x?