Questions about the execution speed and memory usage of algorithms, data structures, languages and libraries.
3
votes
1answer
46 views
f-blas-lapack is twice as fast as MKL for complex numbers
I'm solving the Helmholtz equation using PETSc. I found with the PETSc configure option --download-f-blas-lapack my program runs twice as fast over running it with MKL. Is this a common trend or are ...
3
votes
0answers
39 views
Prediction model on GPU
I am doing a small project at school. I have done my code implementations in CUDA and did some performance measurements with real values, i.e. running the program with different number of threads, ...
2
votes
2answers
41 views
Speedup prediction of rotating mask filter
I am trying to do the speed up analysis of the rotating mask filter (section 4.2.3).
Let $N^2$ be the pixels in the image and let $m^2$ be the neighborhood of a given pixel, what I have for my ...
8
votes
2answers
111 views
How do Volkov and Demmel experimentally determine the latencies, line sizes, and page sizes of a GPU?
In "LU, QR and Cholesky Factorizations using Vector Capabilities of GPUs", by Vasily Volkov and James Demmel, there is an interesting way to interpret the latencies, line sizes, and page sizes of a ...
3
votes
3answers
98 views
How do I get reliable timing data for time spent in function calls in my code?
This question is a follow-up to Fortran: Best way to time sections of your code?.
If I want to time functions in my code, I know I could use gprof or kcachegrind. I also know that the results from ...
3
votes
1answer
139 views
Effecient CFD programming techniques
I'm trying to make highly efficient CFD programming complex for solving combustion problems. I've finished writing core which realises mathematical model, and now I'm concerned about code performance. ...
6
votes
1answer
133 views
What is the impact of C++11 move semantics in the context of scientific computing?
C++11 introduces move semantics which can, for example, improve code performance in situations where C++03 would need to perform a copy construction or copy assignment. This article reports that ...
14
votes
0answers
148 views
How does the performance of Python/Numpy array operations scale with increasing array dimensions?
How do Python/Numpy arrays scale with increasing array dimensions?
This is based on some behaviour I noticed while benchmarking Python code for this question: How to express this complicated ...
5
votes
5answers
183 views
Evaluate the sum
I want to evaluate the sum $$\sum_{k=1}^\infty \left(\frac{i+1}{\sqrt{2}}\right)^k\cdot k^{-\alpha}$$ where $i=\sqrt{-1}$ and $\alpha\in[\frac{3}{4},1]$ with 8 digits accuracy.
If I am willing to ...
10
votes
4answers
169 views
Calculation of the sparsity structure for finite element matrices
Question: What methods are available to accurately and efficiently calculate the sparsity structure of a finite element matrix?
Info: I'm working on a Poisson Pressure Equation solver, using ...
2
votes
0answers
73 views
Cusp Library performance worse than PETSC (GMRES 200 iterations) Why?
I wanted to compare the speeds of the GMRES implementations in the CUSP and the PETSc libraries.
The matrix (A) used for testing was a 3d Laplacian matrix obtained by using the 7 point stencil on a ...
9
votes
1answer
122 views
Statistical models for local memory/compute, network latency, and bandwidth jitter in HPC
Parallel computation is frequently modeled using a deterministic local rate of computation, latency overhead, and network bandwidth. In reality, these are spatially variable and non-deterministic. ...
7
votes
2answers
143 views
Literature references for modeling current and future energy costs of floating-point operations and data transfers
I am searching for the most important literature and slide references for modeling current and future energy costs of floating-point operations and data transfers across the CPU, memory, network, and ...
6
votes
2answers
304 views
Memory usage in fortran when using an array of derived type with pointer
In this sample program I'm doing the same thing (at least I think so) in two different ways. I'm running this on my Linux pc and monitoring the memory usage with top. Using gfortran I find that in the ...
4
votes
1answer
151 views
How to get sparse complex matrices from my code to PETSc efficiently
What is the most efficient way to get a complex sparse matrix from my Fortran code to PETSc? I understand that this is problem dependent, so I tried to give as many relevant details as possible below.
...
5
votes
1answer
81 views
Open source implementation of rational approximation to a function
I am looking for some open source implementation (any of Python, C, C++, Fortran is fine) of rational approximation to a function. Something along the article [1].
I give it a function and it gives me ...
4
votes
1answer
65 views
Efficient way to find max height repetitive sub-trees in an object tree
I am trying to solve a problem of finding a max repetitive sub-tree in an object tree.
By the object tree I mean a tree where each leaf and node has a name. Each leaf has a type and a value of that ...
8
votes
2answers
214 views
Fastest way to find eigenpairs of a small nonsymmetric matrix on a GPU in shared memory
I have a problem where I need to find all positive (as in the eigenvalue is positive) eigenpairs of a small (usually smaller than 60x60) nonsymmetric matrix. I can stop calculating when the eigenvalue ...
3
votes
2answers
88 views
Efficiently changing basis on many diagonal matrices
I have to perform a [complex] basis transformation on a large number of [real] diagonal matrices:
$$ \langle b_i | A | b_j \rangle = \sum_k \langle b_i | \bar{b}_k\rangle \langle\bar{b}_k | A | ...
5
votes
2answers
156 views
How should I report profiling/timing information about my code?
I've seen a lot of publications in Computational Physics journals use different metrics for the performance of their code. Especially for GPGPU code, there seems to be a great variety of timing ...
18
votes
3answers
636 views
What tools or approaches are available to speed up code written in Python?
Background: I think I might want to port some code that calculates matrix exponential-vector products using a Krylov subspace method from MATLAB to Python. (Specifically, Jitse Niesen's expmvp ...
4
votes
1answer
115 views
Intersection of hyperplanes
A very basic question but i couldn't find another post about it:
Given $p$ non parallel hyper-plane in $\mathbb{R}^p$:
$\left(\begin{array}{cccc}
c_{11} & a_{11} & .... & a_{1p} \\
... ...
7
votes
2answers
164 views
What is the overhead in sparse matrix multiplication
Does matrix multiplication (both Mat*Mat, and Mat*Vec) scale with number of non-zeros, or with the size of the matrix? Or some combination of the two.
What about with shape.
For example, I have a ...
3
votes
2answers
255 views
How should I build a 2D 5-point stencil Laplacian matrix in parallel?
I'm making a simple eigenvalue solver with SLEPc, using a 5-point stencil and the finite difference method. I want to be able to assemble the matrix in parallel.
My first thought was just to use ...
9
votes
3answers
219 views
How to implement efficient indexing function for two particle integrals <ij|kl>?
This is a simple symmetry enumeration problem. I give the full background here, but no knowledge of quantum chemistry is needed.
The two particle integral $\langle ij|kl\rangle$ is:
$$
\langle ...
8
votes
3answers
1k views
MATLAB matrix multiplication (the best computational approach)
I have to make a coordinates transformation between two reference systems (axes). For it, three matrices (3x3) have to be multiplied due to some intermediate axes being used. I have thought about two ...
26
votes
8answers
2k views
What are some good strategies for improving the serial performance of my code?
I work in computational science, and as a result, I spend a non-trivial amount of my time trying to increase the scientific throughput of many codes, as well as understanding the efficiency of these ...
9
votes
3answers
726 views
Portable multicore/NUMA memory allocation/initialization best practices
When memory bandwidth limited computations are performed in shared memory environments (e.g. threaded via OpenMP, Pthreads, or TBB), there is a dilemma of how to ensure that the memory is correctly ...
4
votes
3answers
84 views
Whats wrong with my running time calculation?
I am running a linear algebra iterative method (PCG) for solving Ax=b, the dimension of the matrix is 10000x10000.
So, I did 2 preliminary analyses:
Memory Analysis
The size of the matrix ...
5
votes
3answers
494 views
Are DAXPY, DCOPY, DSCAL overkills?
I have implemented CG in FORTRAN by linking it to Intel MKL.
When there are statements like:
(Refer Wikipedia)
p=r;
x=x+alpha*p
r=r-alpha*Ap;
or similar ...
2
votes
2answers
324 views
Contiguous prime numbers with MPI (Want more ideas for an efficient algorithm)
I am a programmer. I am working with Message Passing Interface (MPI) in C. I do a program that consist on finding the contiguous prime from 1 to 10,000,000.
I already do it! but I do it with trial ...
8
votes
5answers
553 views
To what extent is generic and meta-programming using C++ templates useful in computational science?
The C++ language provides generic programming and metaprogramming through templates. These techniques have found their way into many large-scale scientific computing packages (e.g., MPQC, LAMMPS, ...
12
votes
4answers
594 views
When should I use C++ expression templates in computational science, and when should I *not* use them?
Suppose that I'm working on a scientific code in C++. In a recent discussion with a colleague, it was argued that expression templates could be a really bad thing, potentially making software ...
8
votes
2answers
1k views
Octave: calculate distance between two matrices of vectors
Suppose I have two matrices Nx2, Mx2 representing N, M 2d vectors respectively.
Is there a simple and good way to calculate distances between each vector pair (n, m)?
The easy but inefficient way is ...
6
votes
2answers
504 views
Understanding OpenCL performance
I'm using ViennaCL's interface to Eigen as a way to leverage OpenCL. Specifically, I'm using the ::viennacl::linalg::bicgstab_tag with an Eigen sparse matrix. ...
6
votes
2answers
179 views
How do I compute the parallel overhead of a parallel code run on a single processor when no sequential code is available?
I'm profiling the performance of PETSc's linear solvers. As I understand it,
$$\text{speedup}=\frac{\text{Sequential Time}}{\text{Parallel Time}}.$$
I know that running the parallel code on one ...
1
vote
1answer
167 views
How to measure the overall performance of a PETSc program using the -log_summary flag?
When I run a PETSc example in parallel with the flag "-log_summary", the first two tables of information look something like this:
...
19
votes
4answers
5k views
How does the MATLAB backslash operator solve $Ax=b$ for square matrices?
I was comparing a few of my codes to "stock" MATLAB codes. I am surprised at the results.
I ran a sample code (Sparse Matrix)
...
7
votes
4answers
739 views
FLOP counting for library functions
When evaluating the number of FLOPs in a simple function, one can often just go down the expression tallying basic arithmetic operators. However, in the case of mathematical statements involving even ...
5
votes
2answers
234 views
Filtering a dataset to get a more uniform distribution for neural network training
I'm looking into using artificial neural networks (ANN) to predict the reaction rates in my fluid instead of solving the full system of stiff ODEs. Some people from my lab have already done some work ...
7
votes
2answers
277 views
Which Sparse Matrix Solver Libraries can I run on Android?
The title says most of it.
I'm looking for a lightweight and easy-to-use library that I can use for Android (NDK) projects.
For dense stuff I like using Eigen but I haven't found many comprehensive ...
2
votes
1answer
70 views
Low performance on sge cluster
I'm having an issue with my project. When I run the code of Monte-Carlo simulation, on the local server (the machine in my office) it runs on a rate of roughly 100000 steps per 24 hours. When I run it ...
1
vote
0answers
70 views
Constraint solving over modular domains
I have a set of constraints over modular domains e.g. $\exists a \in A_i : x \equiv a \pmod{n_i}$ for all $i=0,\ldots,k$
The question is, does such an $x$ exist? I've been pointed to method of ...
5
votes
4answers
295 views
When analyzing a parallel algorithm, how do you take communication costs into account?
My question is related in spirit to "Is algorithmic analysis by flop counting obsolete?". Counting the number of computational operations in an algorithm is commonly used as a first-order model to ...
5
votes
2answers
192 views
What guidelines should I use when choosing a scalable linear solver?
There are many different linear solvers, some which work best for diagonally dominant matrices, some for symmetric, some for positive definite ones, some for banded matrices, etc... There are direct ...
11
votes
3answers
368 views
Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?
Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices?
For example, if each $D_i$ is ...
6
votes
4answers
248 views
(How) do you take into account memory fragmentation?
I use an example from finite element theory, but anybody who maintains a large datastructure and successively extends it will find something similar.
Suppose I have an unstructured mesh of points and ...
7
votes
3answers
161 views
In what application cases are additive preconditioning schemes superior to multiplicative ones?
In both domain decomposition (DD) and multigrid (MG) methods, one may compose the application of the block updates or coarse corrections as either additive or multiplicative. For pointwise solvers, ...
11
votes
4answers
264 views
How to deal with too much data?
Our plasma dynamics simulations often produce too much information. During the simulations we record various physical properties on a grid (x,y,z,t) that is as large as (8192x1024x1024x1500), for at ...
3
votes
2answers
2k views
Intel Fortran Compiler: tips on optimization at compilation
I will start with my personal experience in our lab. Back in the ifort 9 and 10 days, we used to be quite aggressive with the optimizations, compiling with -O3 and processor specific flags (-xW ...
