Questions tagged [performance]
Questions about the execution speed and memory usage of algorithms, data structures, languages and libraries.
170
questions
2
votes
0
answers
72
views
OpenMP Fortran array operations in target regions
I am asking this here for the possibility that someone here is familiar with OpenMP offloading. Is there some other way to parallelise Fortran array operations outside of unrolling the loops of the ...
- 131
1
vote
0
answers
83
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 ...
- 281
5
votes
1
answer
209
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
12
votes
2
answers
988
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,921
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
129
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 ...
- 461
3
votes
0
answers
181
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
81
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, ...
- 181
1
vote
0
answers
70
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
89
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
200
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), ...
- 152
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
30k
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
98
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
143
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,855
1
vote
1
answer
1k
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
62
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,930
2
votes
0
answers
190
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
105
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
352
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
615
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
657
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
71
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
97
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
200
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
138
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
75
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
564
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
473
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
510
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,602
1
vote
1
answer
176
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
125
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
273
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,145
3
votes
1
answer
461
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
8k
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
644
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
665
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
305
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
506
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 ...
- 985
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
206
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
696
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
654
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