Questions tagged [performance]
Questions about the execution speed and memory usage of algorithms, data structures, languages and libraries.
169
questions
1
vote
0
answers
75
views
Resource to learn assembly code
I'm a PhD student in mechanical engineering and I have to perform a lot of simulations for my project. In my lab we use several well-known libraries, from FEM to machine learning. As we're doing ...
- 231
5
votes
1
answer
131
views
Block-Tridiagonal Matrices with tridiagonal blocks
The Setup
Using finite differences to discretize the 2d diffusion equation $$\partial_tu=\partial_x\left(A\partial_xu+B\partial_yu\right)+\partial_y\left(B\partial_xu+C\partial_yu\right)$$ we get a ...
- 153
11
votes
2
answers
869
views
Faster Logistic Function
I've noticed that a fairly significant number of cycles in one of my programs are being consumed by the logistic function:
$$f(x)=\frac{1}{1+e^{-x}}$$
Is there a good approximation I can use to reduce ...
- 3,606
9
votes
2
answers
2k
views
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?
I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
0
votes
1
answer
100
views
Efficiently solving SDP relaxation of an integer quadratic program
I have an integer quadratic program of the form,
\begin{align}
\underset{x}{\max}&\;\;\|Ax-b\|_2^2\\
\text{subject to}&\;\;x\in{\bf Z}\geq0
\end{align}
I'm currently using the (admittedly ...
- 443
3
votes
0
answers
169
views
How can I improve this matrix product calculation in OpenCL?
I am trying to compute a matrix-matrix product of N stacked complex double N x N matrices. For simplicity, I assume N = 512. I have written code in C++ parallelized with OMP and using OpenBLAS for the ...
- 31
1
vote
0
answers
72
views
Implementation of integration schemes for ordinary differential equations in Python and peformance comparison
I look for a book/manual where I can find implementations of different integration schemes for ordinary differential equations (like 4-th order Runge-Kutta) in Python with Numba.
To be more specific, ...
- 171
1
vote
0
answers
63
views
Calculating the number of Flops of SPH density calculation
I would like to calculate the number of floating point operations (Flops) my code is performing in my machine. To do so, I would like to be sure I am counting the operations in the inner-most loop ...
- 121
25
votes
8
answers
5k
views
Is it possible for user written algorithms to outperform libraries' built-in optimized functions?
I've always had this question in mind (even if it may sound vague), but in my numerical analysis courses we've always learned how to analyze and optimize code. However, since most linear algebra ...
- 353
-2
votes
1
answer
87
views
How to get 10 in computer science, using the number 4 exactly four times, and two signs exactly and two operation + exactly? [closed]
How to get 10 in computer science, using the number 4 exactly four times, and two signs exactly and two operation + exactly ?
- 11
0
votes
1
answer
182
views
What are the advantages and disadvantages of using norm error control in the MATLAB ODE suit?
In MATLAB's ODE suit, there seem to be two basic methods of controlling the Local Truncation Error (LTE) of the ODE which the user can choose from, namely:
The absolute error control (default), ...
- 142
2
votes
1
answer
43
views
In Eigen, can a sparse matrix contain vectors/objects instead of simple scalar values?
I need to have a sparse matrix whose elements are not simple numbers, but objects, e.g. a couple of floating point values and a bunch of integer indices.
I am wondering if Eigen has something similar, ...
- 171
12
votes
3
answers
23k
views
How to properly calculate CPU and GPU FLOPS performance?
Problem
I'm trying to calculate CPU / GPU FLOPS performance but I'm not sure if I'm doing it correctly.
Let's say we have:
A Kaby Lake CPU (clock: 2.8 GHz, cores: 4, threads: 8)
A Pascal GPU (clock: ...
- 221
1
vote
1
answer
95
views
An efficient algorithm to find Nearest Neighbours
So imagine I have a $m$ vectors each of dimension $d$. Lets call them, $\vec x_{i}$, with $i = 1, 2, 3, 4, 5, \dots, m$. Now the idea is to find the neighbours of $\vec x_{i}$ (calling them $\vec x_{j}...
- 263
5
votes
1
answer
141
views
Accurate and efficient computation of the logarithm of the ratio of two sines
For exploratory work related to special function implementations, I need to compute $\log \frac{\sin y}{\sin x} $, where $0 \le x \le y \le 2x < \frac{\pi}{2}$. Cases with $x \approx y$ in ...
- 1,340
1
vote
1
answer
925
views
How to calculate the number of floating point operations a task/ process requires? (not FLOP/s, but FLOP)
There have been many papers quoting FLOP to quote the performance of a specific approach in machine learning. For example,
We trained two models with different capacities: BlazePose Full (6.9 MFlop, ...
- 111
1
vote
0
answers
52
views
Why are "instructions retired" more stable than "cycles" or "task-clock" when using "perf"?
I tested the perf tool in Ubuntu 18.04 on a simple benchmark in our compiler (parsing some file). I ran perf several times and ...
- 2,900
2
votes
0
answers
164
views
Whi are chi-squared distributions in (C++) boost::random and C++ STL faster than in boost::math?
I am trying to generate random chi-squared numbers in C++, according to some degree of freedom (which can be a float). Several libraries can be used for that purpose, among which the C++11 Standard ...
- 153
1
vote
0
answers
103
views
Fastest way to solve linear programming with 6 complex inequalities and 5 nonnegative variables
I have a program where I need to solve a linear programming problem in a fast loop. The language I'm using is Java and any kind of bindings to other languages are not acceptable. Libraries might be ...
- 151
2
votes
1
answer
306
views
Sparse matrix-matrix multiplication using AVX2
I have two sparse general matrices stored in CSR format I need to multiply. Is there any chance to gain performance using AVX2? In general the matrices are big (hundreds of millions of non-zeros and ...
- 840
9
votes
1
answer
2k
views
Increasing computational performance by using 16 bit numbers
I recently found the following article where it was stated that using 16 bit numbers can be used to increase the computational performance of AI applications. According to the article numbers above 16 ...
- 840
0
votes
0
answers
536
views
Parallel plate capacitor as simple superposition of Coulomb-fields
I am trying to calculate and visualize the electric field inside and outside of a parallel plate capacitor by assuming a uniform distribution of point charges on each plate and by adding up the ...
- 11
4
votes
2
answers
619
views
Fastest Way to Mutiply $10^4$ 2x2 Matrices
In a code that I work with (written in python, but also tagging as matlab because numpy is so close and I could use it if need be), we use a transfer matrix method to compute the properties of a ...
2
votes
0
answers
70
views
Avoid matrix multiplication in algebraic multigrid method
Currently when I try to solve a linear algebra system of the form of $A x =b$ I use the algebraic multigrid method. The algebraic multigrid method uses a Galerkin product to form the coarse grid ...
- 840
4
votes
1
answer
96
views
Is operation count a reliable predictor of performance when comparing two formulations?
I have two formulations to solve a problem (both give dense, complex and symmetric system). They are solved multiple times in a loop. I am trying to predict which is better to use.
The first one ...
1
vote
0
answers
23
views
Speedup of CPU Pipelining by number of steps [closed]
When a CPU has $K$ steps the speed up of using pipelining compared to non-pipelining is $K$. But what I want to know is, say I am a CPU designer and want to decide whether I should build $K$ or $N$ ...
1
vote
1
answer
188
views
Vectorization of Jacobi iteration
Assume I have a linear system of $A x = b$ which I want to solve with Jacobi iteration. Matrix $A$ is given in CSR format. The vectors are dense.
The code for Jacobi iteration is quite clear and can ...
- 840
2
votes
1
answer
136
views
Efficiently finding binary vectors satisfying multiple conditions
I am trying to solve the following problem:
Given a binary matrix $\mathbf{A} \in \{0,1\}^{m \times n}$ and a vector $\mathbf{b} \in \mathbb N^n$, does there exist a binary vector $\mathbf{c} \in \{0,...
- 23
1
vote
1
answer
74
views
How to avoid unnecessary checks when inverting this LU decomposition
Background for the question
I am currently working on a Matlab code in which the systems of linear equations $Ax_1 = b_1$, $Ax_2 = b_2$, ... have to be solved. As the matrix $A$ is constant during ...
- 115
2
votes
1
answer
538
views
Implementation of Jacobi iteration
I have implemented the Jacobi iteration in C++ using a dense vector and a sparse matrix in CSR format. The code is as follows:
...
- 840
4
votes
1
answer
449
views
Improve Mandelung constant code
I'm learning and improving my Python skills.
I did a program in Python about Mandelung constant. But, I'm having kind of a problem.
The Mangelung constant is calculated using this sum:
$$ V_{total} =...
- 43
6
votes
0
answers
451
views
Is there any catch on using `zgemm3m` vs regular `zgemm`?
I've just (to my embarrassment) encountered a BLAS-like extension of a matrix-matrix product subroutine gemm in Intel MKL: gemm3m...
- 8,572
1
vote
1
answer
165
views
How to implement this even-odd matrix decomposition efficiently?
Note: This question has also been asked on stackoverflow - see https://stackoverflow.com/questions/57197910/how-to-implement-this-even-odd-matrix-decomposition-efficiently?noredirect=1#...
- 115
2
votes
2
answers
114
views
Time complexity analysis
I want to know the time complexity of following code
Say I have a list unique_element[]
There is an array which contain elements {4,5,2,4,7,8,1,5,9,8,1}
Now as per my code I want to find out the ...
- 123
6
votes
1
answer
254
views
Whittaker-Shannon interpolation: Accuracy dies with speedup; can it be fixed?
With a truncated Whitaker-Shannon series (cardinal series)
$$
f(t) = \sum_{j = 0}^{n-1} y_{j} \frac{\sin\left(\pi( \frac{t-t_0}{h} -j)\right)}{\pi\left(\frac{t-t_0}{h}-j\right)}
$$
we can naively ...
- 2,085
3
votes
1
answer
444
views
Radiation heat transfer between surfaces
I'm trying to model the temperature distribution over a curved surface. Apart from the heat equation, I need to take into account the energy emission/absorption through electromagnetic radiation. The ...
- 31
6
votes
2
answers
2k
views
Fast and Numerically Stable Pairwise Distance Algorithms
I'm looking for resources on fast, numerically stable pairwise euclidean distance algorithms. In particular, suppose $A \in \mathbb{R}^{M \times D}$ and $B \in \mathbb{R}^{N \times D}$ are two sets of ...
9
votes
2
answers
7k
views
Integer operations vs floating point operations
I have been working with an algorithm, which uses
additions of floating point vectors,
(sparse matrix of floats)x(dense vector of floats) dot products
I recently found out that I can get the same ...
3
votes
1
answer
588
views
MKL/FFTW performance of batch 1-D FFTs
MKL and FFTW offer 1-D FFTs that can operate on many inputs simultaneously - in other words, they can batch-transform the columns of some input matrix. Is the performance of these multi-transforms ...
- 663
3
votes
1
answer
568
views
What is the fastest way to solve Ax=b (subject to constraints and an absolute term)
I am trying to solve/optimize $Ax=b$ in the least squares sense subject to
box constraints;
a few (less than 5) equality/inequality constraints; and
an absolute function penalty (or some other ...
- 133
0
votes
1
answer
296
views
CPU and GPU influence on task parallel execution performance
This question is mainly about hardware, but also about software.
In my current work I have approximately 68 millions of combinations that I am iterating through, in parallel. For each of those ...
- 101
1
vote
1
answer
2k
views
General understanding of Intel MKL, threads and MPI
Preface
I seem to lack a fundamental understanding of best practise recommendations given by Intels MKL user guides for using MKL in threaded applications. So let's clarify it together.
Wording and ...
- 113
2
votes
1
answer
489
views
Potential gain - Matlab vs C/C++ - assembly and eigenvalues
I have a Matlab code computing the solution to an eigenvalue PDE. It consists of two parts: assembly of the stiffness/rigidity matrices and solving a generalized eigenvalue problem. I mention that the ...
- 965
1
vote
1
answer
2k
views
Kronecker product among multiple arrays
I was wondering whether there is a smart and efficient way in Matlab to compute the kronecker product of several 1D arrays.
What I mean is something like this
...
- 133
1
vote
2
answers
202
views
Sign of integer determinant 4 by 4
I'm in the context of this publication: http://www.gilbertbernstein.com/resources/booleans2009.pdf
I applied quantization to my point coordinates: All coordinates are integer lying in [0, 2 power 20]....
- 111
6
votes
1
answer
2k
views
Loop optimization with f2py, Cython and Numba
I tried to used f2py, Cython and Numba to make a simple loop structure be faster in python. Python implementation:
...
- 193
1
vote
1
answer
619
views
Efficiency of Array Slicing
I have large arrays of data organized so that it can be processed efficiently using array processing libraries. However, there are times when I only need to process slices of the arrays where a slice ...
- 111
1
vote
0
answers
647
views
Vectorizing Matrix Multiplication
I would like to do the following operation: I have a "4D" matrix A and a "3D" matrix B. Both A and B are actually 2D matrices, where for A, each element is a 2D matrix, and for B, each element is a 1D ...
- 105
0
votes
1
answer
158
views
Find hidden sequence $a_n = a_{n-1} + T $ , with period $T$, given some "random" numbers
I have this data plotted on a graph in which all points have the same value on the y-axis, e.g a constant integer "c", while the x-axis is the time in seconds.
So, for a c = 25 on the y-axis, there ...
- 101
3
votes
1
answer
2k
views
Why is the speed of the parts of the LU-decomposition so different?
I know that an easy way to solve the matrix problem
$$A\cdot x=b$$
is the LU decomposition
$$\begin{split}
L,\,U&=\text{lu}(A)\\
y&=\text{solve}(L,\,b)\\
x&=\text{solve}(U,\,y)
\end{split}$...
- 543