Questions tagged [efficiency]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
27
votes
3answers
8k views

What is the computational cost of $\sqrt{x}$ in standard libraries?

One of the major issues that we have to deal with in molecular simulations is the calculation of distance-dependent forces. If we can restrict the force and distance functions to have even powers of ...
15
votes
3answers
7k views

What are the advantages and disadvantages of the particle decomposition and domain decomposition parallelization algorithms?

I am running molecular dynamics (MD) simulations using several software packages, like Gromacs and DL_POLY. Gromacs now supports both the particle decomposition and domain decomposition algorithms. ...
15
votes
3answers
2k views

I/O Strategies for computational problems with large data sets?

My research group focuses on molecular dynamics, which obviously can generate gigabytes of data as part of a single trajectory which must then be analyzed. Several of the problems we're concerned ...
13
votes
2answers
870 views

When is automatic differentiation cheap?

Automatic differentiation allows us to numerically evaluate the derivative of a program on a particular input. There is a theorem that this computation can done at a cost less than five times the cost ...
12
votes
2answers
2k views

What is the most efficient way to write 'for' loops in Matlab?

I have read that if, for example, I have a double for loop that runs over the indexes of a matrix, then putting the column running index in the outer loop is more ...
12
votes
1answer
432 views

Costs of lookups versus calculations

I am interested in setting up calculations to check if a distance criterion is satisfied: that is, the distance between a vector ${\bf x}_i$ and anther vector ${\bf x}_j$ should be less than some ...
10
votes
3answers
842 views

Is there a complexity between $O(n)$ and $O(n \log n)$ [closed]

Is there a complexity degree that is bigger than $O(n)$ and smaller than $O(n \log n)$?
10
votes
4answers
3k views

Fast and accurate double precision implementation of incomplete gamma function

What is the state of the art way of implementing double precision special functions? I need the following integral: $$ F_m(t) = \int_0^1 u^{2m} e^{-tu^2} d u = {\gamma(m+{1\over 2}, t)\...
10
votes
3answers
8k views

Nvidia K20X vs GeForce Titan for GPGPU acceleration

Im trying to understand the difference between these two graphics cards for academic computing, specifically for the DGEMM component. If we look at the raw statistics, both have the same GK110 chip, ...
8
votes
1answer
337 views

Accurate and efficient computation of the inverse Langevin function

The Langevin function $\mathcal{L}(x) = \mathrm{coth}(x) - \frac{1}{x}$ occurs in computations related to elastomers and paramagnetic materials. It is easily computed accurately and with high ...
7
votes
2answers
325 views

Comparing various implementations/software packages for large-scale finite element simulations

I currently use FEniCS and Deal.II to solve various FEM problems. I am also writing my own implementation of these problems by directly implementing the data structures, routines, and solvers within ...
7
votes
3answers
915 views

Is there any computational efficiency to global variables?

I'm wondering specifically in regard to a recursive function such as massive a game tree. I can't specifically say how big yet, but definitely pushing the limits of a given processor or processor ...
5
votes
4answers
2k views

What is "good" parallel scaling?

I often hear the phrase "good" or "bad" parallel scaling/efficiency. What exactly do people mean when they say that? For example, let $p = 1,\ldots 16$ be the number of processing elements, and A and ...
5
votes
3answers
267 views

How to efficiently structure simulation data in memory for cells with varying degrees of freedom?

For a discontinuous Galerkin-based simulation I need to store cell-based simulation data in memory. Since the order of the polynomial approximation $N_p$ may vary between cells, I wonder what the most ...
5
votes
1answer
377 views

Fastest way to calculate the $2$-norm (or an upper bound for the $2$-norm) of the inverse of a matrix $A\in \mathbb{C}^{N\times N}$

I have a matrix $A\in \mathbb{C}^{N\times N}$ and I need to calculate $||A^{-1}||_{2}$ efficiently. Can it be done without having to evaluate the inverse explicitly? In general, I am looking for ...
5
votes
1answer
692 views

Half precision in Fortran

To improve the time efficiency of my code, I'd like to test a lower precision for real number, using e.g. half precision (2 bytes). However, I'm not sure if I can do that in Fortran. After playing ...
4
votes
2answers
182 views

Efficiency of Repeated Sparse Matrix-Vector Products

I recently read Wolfgang's answer to the question found here and found myself wondering about a related followup question. Assume you have two sparse matrices $A$ and $B$. You need to do the ...
4
votes
2answers
88 views

How to efficiently invert $K \otimes M+I_T\otimes \Sigma$?

I'm looking for a way to efficiently invert $$K \otimes M+I_T\otimes \Sigma$$ where the inverses for $M,K$ exist. $I_T$ is the identity matrix of dimension $T$, and $\Sigma$ is a diagonal matrix, with ...
4
votes
2answers
186 views

MATLAB Matrix Multiply Efficiency

I am using MATLAB to prototype a few matrix multiply techniques and compare efficiency. Eventually, I will move the prototype codes to C. It is for a homework assignment where we need to write an ...
4
votes
1answer
137 views

Efficient way to generate a list of possible matrices (all integer components) with a determinant $V$

I have an interesting problem from my research that I have been struggling to solve. One part of the problem involves generating all possible matrices, where each set contains three integer vectors, ...
4
votes
1answer
2k views

calculation time in Fluent

I'm making a model of a square box where water comes in and the water level rises. I want it to be a transient, turbulent, VOF-model. The velocity of water entering changes in time ($-0.2$ to $0.2$ m/...
3
votes
3answers
150 views

Inverse compression for space-time trade off

A bit of a strange question - but I am developing an application where speed is critical, not memory - I have the ability to blow up to 3 TB on the data storage that this application will use and I am ...
3
votes
2answers
886 views

How to re-use the coefficient matrix decomposition result when solving linear systems by Eigen C++

My problem needs to solve dense symmetric linear systems something like: A x = b, A y = x, ...
3
votes
1answer
123 views

How to justify using available code (in different language) for comparing algorithms

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm from the literature. Our algorithm is in MATLAB, ...
3
votes
1answer
111 views

Solve $A^{-1} b$ when one column is replaced

Given square matrix $A_0$, vector $b$, vector $A_0^{-1}b$ and matrices $A_1, A_2, \dots, A_k$, in which each $A_i$ is generated from $A_{i-1}$ by replacing one single column, I would like to find an ...
3
votes
1answer
106 views

How can I extract the banded or block diagonal part of a sparse matrix in MATLAB?

Given a large sparse (square) matrix in MATLAB, how can I extract the banded or the block-diagonal parts (of fixed size) of it efficiently? These are useful operations when prototyping and testing ...
2
votes
2answers
95 views

How to measure efficiency of the differential equations solver

I want to compare a few solvers of partial differential equations. I need to include the computational time and the solution accuracy (compared to analytical solution or something similar). What kind ...
2
votes
2answers
176 views

Why the same program runs faster on an older computer?

I have the same single thread problem, which is something like a simple ...
2
votes
1answer
175 views

Solving stiff ODEs: Dealing with Jacobian terms which take too long to compute with finite differences

I have a system of PDEs describing atmospheric chemistry and transport. I use finite-differences to make my system of PDEs into a system of ~10,000 ODEs. I then integrate the ODEs forward in time with ...
2
votes
1answer
143 views

Methods to improve the efficiency and the memory requirement of LU factorization for complex symmetric system matrix

I want to solve a linear set of equations (Ax=b) using LU decomposition. My "A" matrix is a complex matrix which is ...
2
votes
1answer
134 views

Parallel efficiency

I would like to calculate efficiency of parallel alghoritm, using the number of computations instead of time computations. In materials from my studies I have a formula like below: $$ \eta(n,p) = \...
2
votes
1answer
179 views

Performance based on the Roofline model

To somewhat follow up on the question asked here, I have been told that the Roofline model is one way of assessing the performance of any scientific code. Basically I compute the Arithmetic Intensity (...
2
votes
1answer
72 views

What is the fomula of polynomial time of solving positive definite symmetric linear system

For a positive definite symmetric linear system, Cholesky decomposition based method should be the best solver which has a rough n^3/3 flops requirement. What is ...
2
votes
2answers
745 views

Modern Computer Efficiency vs Modern Nervous Systems

I am currently working on an evolutionary system and most of what I have heard is that a computer like mine at the moment would be able to simulate a bee sized brain (not taking into account the time ...
2
votes
1answer
180 views

Difference between Brent's and Alefeld-Potra-Shi for root finding

I need to find the (unique) root of a nonlinear function $f(x)$, $x \in \mathbb{R}$. For the record, $f(x)$ is the CDF of a probability density minus a constant $0 < p < 1$ (I am inverting the ...
2
votes
1answer
686 views

Efficient formulation of an SDP involving L1 norm

I am trying to reformulate the following problem to be solved efficiently (by MOSEK) $$ \min_{X} \text{Tr}(CX)+\lambda\sum_{i,j}|x_{i,j}| \\ \text{s.t.} \quad ||X||_F\le1 \quad \text{and} \quad X\ge 0 ...
2
votes
1answer
511 views

Trying to implement a simple/efficient combinations function in MATLAB

So, recently, I have found myself in the position of having to implement a combinations function in MATLAB. What I mean by this is the following: I simply need to list all possible combinations for an ...
1
vote
2answers
75 views

Help on writing sofware: general guidelines, in particular separation of computation and visualization

Although I already did some work in the intersection of theory and simulation I'm still very new to this field and I need some guidance. If anybody can give some recommendations for introductory ...
1
vote
1answer
94 views

Declare variable to substitute one calculate only once

Frame of the question I am currently editing an add-on module to an ocean/circulation model, which is written in Fortran. The code of the main model is quite optimized with respect to short run time (...
1
vote
1answer
44 views

Effecient method for iterating over sparse dataset

Apologies if this isn't the appropriate forum for this question. I have a set of elements that I need to iterate over as part of a modeling workflow. The elements exists over a set of dimensions (i, ...
1
vote
1answer
375 views

Why does PETSc matrix memory allocation improve performance so much?

Context In the Portable, Extensible Toolkit for Scientific Computing (PETSc), the user often creates matrices and vectors. These objects are then used as input for other routines like iterative ...
1
vote
1answer
146 views

Plotting the same function multiple times on the same set of axes but with different parameters [Python]

I am currently trying to plot a function which describes linear perturbation growth in cosmology for different world models. I would like to be able to have all the curves on the same set of axes, but ...
1
vote
1answer
116 views

Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming

In combinatorial optimization, there are many problems that can be formulated as either Network Flow model or Mixed Integer Programming (MIP), e.g. supply chains, transportation, and graph-base ...
1
vote
0answers
151 views

Why is the method of im2col with GEMM is more efficient than the method of direction implementation with SIMD in CNN

The convolutional layers are most computationally intense parts of Convolutional neural networks (CNNs).Currently the common approach to impement convolutional layers is to expand the image into a ...
1
vote
0answers
58 views

B-splines least squares with equality constraints

Can someone recommend the best way to solve a least squares fitting problem with B-splines, with additional equality constraints? I want to solve: $$ \min_x || b - A x ||^2, \textrm{subject to: } C x =...
1
vote
0answers
54 views

Stiff ODEs coupled with PDEs (computational efficiency)

I am simulating in COMSOL a system of 3 coupled PDEs (parabolic & elliptic) along with 10 stiff ODEs. In order to have the system working, I am downsizing the time step size too much to achieve ...
1
vote
1answer
68 views

Calculate proportions of exponentially weighted factors avoiding underflow problem

I am trying to implement in Python this ratio: $\frac{w_t(i)}{\sum w_t(j)}$ where $w_t(i) = w_{t-1}(i)\cdot\exp{(-x_{t}(i))}$, i.e. the weights are exponentially decreasing without running into ...
1
vote
0answers
71 views

What's the most efficient way to calculate the Wiger quasiprobability distribution?

I want to calculate the Wigner quasiprobability distribution function of a particular wavefunction. The definition suggests a few straightforward ways of calculating it, but I was wondering if there's ...
0
votes
3answers
925 views

Determining efficiency in MFLOPS/s of a parallel program

I am running some scientific (parallel) code and would like to obtain some performance profiling measurements. I want to obtain the "efficiency" of the code in terms of flops/s over theoretical (peak) ...
0
votes
2answers
134 views

Benefits of matrix multiply over inversion

I have two variations of an iterative algorithm. All the steps of both algorithms are equivalent except one. In this step: Algorithm 1 needs to compute the matrix $ABA^T$ for matrices $A \in \mathbb{...