33
votes
Accepted
Is it possible for user written algorithms to outperform libraries' built-in optimized functions?
Although LAPACK has some incredibly optimized code, it can still be worth it to write your own version in a few cases.
The most important reason (and the reason they make you do it in your course). ...
- 1,416
21
votes
Accepted
The real myth of GPU (specifically CUDA) really speed up FEM/CFD
Here's the deal with GPUs. On a GPU, every single core is slow. Really slow. However, you have thousands of cores. If you can effectively use the thousands of cores at a time, then your algorithm will ...
- 12.3k
14
votes
Accepted
Beating typical BLAS libraries matrix multiplication performance
Consolidating the comments:
No, you are very unlikely to beat a typical BLAS library such as Intel's MKL, AMD's Math Core Library, or OpenBLAS.1
These not only use vectorization, but also (at least ...
14
votes
Accepted
Hardware performance, floating point functions
In the 1980's era Intel 80x86 architecture, there was a scalar floating point unit that had instructions like FSIN, FCOS, etc. for computing functions like sin and cos. These functions were ...
- 18.5k
14
votes
Accepted
How to compare runtimes of two algorithms in a reproducible way
To make more robust comparisons (on linux), you can :
1) On Intel CPUs the turbo overclocks your CPU. This is controlled by the temperature of the CPU, so it can behave differently from one run to ...
- 368
14
votes
Accepted
Whittaker-Shannon interpolation: Accuracy dies with speedup; can it be fixed?
I was able to reproduce the behavior reported in the question, and traced the observed inaccuracies to the following line:
...
- 1,855
14
votes
Accepted
Increasing computational performance by using 16 bit numbers
There has been considerable recent interest in numerical linear algebra using mixed precision with some combination of 16, 32, 64, and 128 bit floating point arithmetic.
For example, a low ...
- 18.5k
13
votes
Accepted
Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?
BLAS may not have a function to compute what you are asking for, but the product
$$
Y_N = A^TY_AA + B^T Y_B B
$$
means that the entries $(Y_N)_{ij}$ are defined by
$$
(Y_N)_{ij} = \sum_{k,l} (A^T)...
- 54.2k
13
votes
Faster Logistic Function
Yes! There are nice approximations of the logistic.
Plot of Approximating Functions
As shown below, several functions approximate the logistic (shown as blue dots). This graph is available ...
- 3,921
11
votes
Accepted
What is the state of the art algorithm for diagonalizing real symmetric matrices?
The QR/Francis algorithm is the go-to choice for dense eigenproblems, but there are a few competitors around:
The Jacobi algorithm (like QR, another algorithm with an unfortunate name, which can be ...
- 11.1k
9
votes
Accepted
Loop optimization with f2py, Cython and Numba
I think that the problem is linked to the way in which f2py generates the fortran interface: the argument to fortranrun.f2py should be stored as a F_CONTIGUOUS ...
- 3,819
9
votes
How to properly calculate CPU and GPU FLOPS performance?
You can calculate GFLOP rates this way, but the numbers are pretty meaningless on today's hardware:
Floating point operations require a variable number of clock cycles. An addition is generally ...
- 54.2k
8
votes
Accepted
Integer operations vs floating point operations
There is a nice discussion on StackOverflow regarding floating point vs integer operations. In short, the performance of the operations depends a lot on
processor architecture
how the data is stored ...
- 8,602
8
votes
Accepted
Fastest Way to Mutiply $10^4$ 2x2 Matrices
In general, I agree with Chris's comment that using a compiled language with the allocation of the matrices on the stack can help significantly.
Several possibilities if we are limited to Python and ...
- 8,602
8
votes
Is it possible for user written algorithms to outperform libraries' built-in optimized functions?
@ThiysSteel covers a lot, here is another perspective I find important:
Even if you have available excellent implementations of any algorithm you might need, you still need to understand some of the ...
- 181
7
votes
Is it possible for user written algorithms to outperform libraries' built-in optimized functions?
To clarify @ThiysSteel's good answer:
The point is not to attempt to surpass the optimization of code written by very experienced people, who'd wrangled with it for decades.
The point is to acquaint ...
- 171
7
votes
Is it possible for user written algorithms to outperform libraries' built-in optimized functions?
I used to try to optimize code via using assembly language (as opposed to C). I had some clear success, where a real-time microphone array worked with assembly language, but it would not work at all ...
- 171
6
votes
Accepted
Why is the speed of the parts of the LU-decomposition so different?
First, don't forget to also time the LU decomposition in a loop! Otherwise it's not really a fair comparison. If I do that, I get the following timings:
...
- 12.2k
6
votes
Accepted
Implementation of Jacobi iteration
If you really want to speed it up, I'd suggest changing your iteration to a SSOR iteration. This can converge much faster than jacobi, and if you are already OpenMP parallelized, there's not much you ...
- 2,069
6
votes
Accepted
Is operation count a reliable predictor of performance when comparing two formulations?
No. There a number of aspects of modern computer architecture that make operation counts unreliable as a way to compare the performance of algorithms. These include memory caches, vector ...
- 18.5k
6
votes
Is it possible for user written algorithms to outperform libraries' built-in optimized functions?
This might be tangent but i feel it worth adding. A common way for user code to beat libraries is to exploit structure the libraries are not aware of. Block diagonal matrices are easier to work in ...
- 189
6
votes
Faster Logistic Function
If only low-accuracy approximations are needed, it is highly advisable to perform all computation in single precision, for example IEEE-754 binary32 format, usually ...
- 1,855
5
votes
The real myth of GPU (specifically CUDA) really speed up FEM/CFD
To extend Chris Rackauckas's exhaustive answer with a reference try to look pdf by Torres, Gonzalez-Escribano, Llanos. It is about the tuning of a gpu, that is an important aspect for performance.
...
- 1,330
5
votes
Why am I not seeing faster neural network training after upgrading to a vastly better GPU?
I suppose, you right and your network is not that big to 100%-utilize the GPU. The bottle-neck here seems to be not the GPU itself, but the transfer rate between RAM and VRAM and here the difference ...
- 114
5
votes
Integer operations vs floating point operations
Integer operations are generally faster than floating point operations, but the gap is far less than it was, say, 30 years ago when everyone was still counting FLOPS. The difference may be a factor of ...
- 54.2k
5
votes
Accepted
Improve Mandelung constant code
As mentioned by @Richard, loops in Python are slow. Two solutions come to my mind:
Use NumPy and vectorize the operations. This will speed up your calculations at the cost of storing your ...
- 8,370
4
votes
Accepted
Finding all binary vectors with given A-length
Are the entries in your $A$ matrix actually real or just integer? If they are real numbers, how precisely do you need to satisfy the constraint? Are the entries of $A$ all nonnegative, or could ...
- 18.5k
4
votes
Integer vs float multiplication performance, modern CPUs
In general, the answers is no.
Modern CPU's excel at problems which have high arithmetic intensity and are implemented using floating point arithmetic.
A few figures will help explain the ...
- 1,391
4
votes
Accepted
Time complexity analysis
It's O(n), but it depends on the sorting algorithm you use. Finding unique elements is O(n) with a hash table. You use one for loop to count incidents and a subsequent loop to extract uniques.
...
- 3,921
Only top scored, non community-wiki answers of a minimum length are eligible