Skip to main content

# Questions tagged [complexity]

Relating to the level of difficulty of a calculation or the asymptotic running time of an algorithm.

106 questions
Filter by
Sorted by
Tagged with
48 votes
7 answers
6k views

### Is algorithmic analysis by flop-counting obsolete?

In my numerical analysis courses, I learned to analyze the efficiency of algorithms by counting the number of floating-point operations (flops) they require, relative to the size of the problem. For ...
• 16.5k
28 votes
6 answers
6k views

### How can the gravitational n-body problem be solved in parallel?

How can the gravitational n-body problem be solved numerically in parallel? Is precision-complexity tradeoff possible? How does precision influence the quality of the model?
• 383
23 votes
3 answers
3k 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 ...
• 3,959
16 votes
1 answer
1k views

### Complexity of MD simulations

I'm new to molecular dynamics (MD) simulations. What is the complexity of a molecular dynamics simulation in terms of simulation time? In other words, if I want increase the simulated time from 10 ...
14 votes
3 answers
660 views

### Scientific Programming Contests

I regularly compete in so called "Programming Contests", where you solve difficult algorithmic problems with your own code and problem solving skills during a limited time-frame. For referential ...
• 243
13 votes
3 answers
5k views

### Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
• 1,909
13 votes
2 answers
2k views

### Does the "cofactor technique" for inverting a matrix have any practical significance?

The title is the question. This technique involves using the "matrix of cofactors", or "adjugate matrix", and gives explicit formulae for the components of the inverse of a square matrix. It is not ...
• 515
13 votes
4 answers
8k 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 ...
• 1,675
11 votes
2 answers
7k views

### How does the computational cost of an mpi_allgather operation compare with a gather/scatter operation?

I'm working on a problem that can be parallelized by using a single mpi_allgather operation or one mpi_scatter and one mpi_gather operation. These operations are called within a while loop, so they ...
• 12k
10 votes
3 answers
871 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)$?
• 101
10 votes
2 answers
9k 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 ...
9 votes
2 answers
338 views

### Computation Effort of Algorithms

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation ...
• 191
9 votes
1 answer
1k views

### Why is it that SVD routines on nearly square matrices run significantly faster than if the matrix was highly non square?

In Python / Matlab, if you run a routine for SVD on a significantly non-square matrix, X, such as X.shape = (2,15000) you will ...
• 203
9 votes
1 answer
1k views

### N-body simulation optimisation, looking for name or existing work

during the development of my N-body simulation with visualisation in WebGL, I devised an optimisation, and I'm wondering if it has a name. I find it unlikely that it has never been done before. It ...
8 votes
2 answers
7k views

### Why are log and exp considered 'expensive' computations in ML?

In many resources/videos I see comments being made along the lines of "and we can see here that we have a logarithm/exponential so this will be an expensive computation to make." (such as ...
• 183
8 votes
5 answers
29k views

### Computational Complexity of 2D Convolution

I am using image filtering for an image processing algorithm I'm developing. I'm using a predefined Matlab function to do the convolution, but I'd like to know what the computational complexity is for ...
• 293
8 votes
2 answers
1k views

### How does a Sparse Direct Solver know about dimensionality of a problem being solved?

It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively. But how does a ...
• 1,111
8 votes
1 answer
257 views

### Are there improved method of computing the following expression?

given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following ...
• 241
7 votes
2 answers
556 views

### What heuristics can be used to minimize the asymptotic matrix bandwidth of a 5-point Laplacian discretization?

I can see that there are multiple heuristics to achieve a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP-...
• 12k
7 votes
1 answer
362 views

### How does the number of function calls in BFGS scale with the dimensionality of space?

Question Is there any estimate for the scaling of the number of function calls in BFGS-optimization with the dimensionality of the search space? Specifically I am assuming a (free) expression for the ...
• 183
6 votes
2 answers
259 views

### What are the numerical methods for huge polynomial systems?

Let a system of $n$ polynomial equations of degree $d$ with $m$ variables. I'm interested in a sparse system with $d = 3$, $n \sim 2000000$, $m \sim 50000$ and integer coefficients. What techniques ...
6 votes
2 answers
4k views

### Fast algorithms to find the eigenvalues of some matrix on intervals of interest

I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest. Suppose we have an arbitrary $n\times n$ matrix $A$, ...
• 2,552
6 votes
1 answer
714 views

### Poisson solver on unstructured mesh

For the 2D Poisson equation, there exist on finite-difference mesh, some code taking $O(n \log(n))$ operations to solve it on a mesh with $n$ nodes. They rely on Fast Fourier Transform or Block Cyclic ...
6 votes
1 answer
249 views

### Efficient algorithm for a matrix product

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
• 295
6 votes
1 answer
118 views

### Measures of parsimony for numerical models?

There are hundreds of different types of performance measures for numerical models, many of which are applicable to many different types of models. But a good model doesn't just perform well, it ...
• 373
5 votes
3 answers
2k views

### Computational cost of numerical methods for PDEs

Say I need to solve a PDE numerically. Depending on the problem and the numerical method chosen, I can usually see some issues coming: implementation issues (e.g. boundary conditions, parallelization),...
• 1,075
5 votes
1 answer
4k views

### Comparing Algorithmic complexity, ODE Solvers (Big O)

I am currently using the following three methods to solve differential equations: 4th order Runge Kutta Method Euler Method Internal scipy methods: ...
• 153
5 votes
1 answer
353 views

### Complexity of recovering all roots of a polynomial

Given a polynomial of degree n and a list of putative roots $\{r_i\}_{i=1}^{n}$, we can verify that all the putative roots are indeed correct by $n$ applications of Horner's method. Hence verifying ...
• 2,155
5 votes
1 answer
63 views

### correct complexity notation

I have written an algorithm where the 2 input arguments are a file and a list of values. I would like to say the algorithm complexity is: ...
• 153
5 votes
1 answer
228 views

### Is there an efficient algorithm for calculation of continued fraction expansion from decimal digits?

Suppose to calculate the continued fraction expansion of $\pi$, the common-sense algorithm would be to take the decimal part, perform inversion, which will give the next term as integer part, and the ...
5 votes
2 answers
232 views

### Restrict Voronoï diagram to a polygon

I managed to build the Voronoï diagram of n points using Fortune's algorithm. This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point). I'd like to ...
• 151
5 votes
0 answers
540 views

### Optimisation of matrix exponential

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
• 51
5 votes
0 answers
2k views

### Two-chordless cycle extraction from a failed comparability graph recognition

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
5 votes
1 answer
155 views

### complexity constants in median computations same as that of general quantiles?

I would like to know whether the constant in the time complexity of computing the median is different from that of computing general quantiles. In R for example: ...
• 427
4 votes
2 answers
557 views

### Why is computational cost measured in Floating Pt. Ops. in times of parallel computing?

In times of parallel computing, it seems to me that algorithms (also basic ones, like matrix-vector multiplication) should be measured by their dependent steps (that use results from steps before) ...
• 799
4 votes
1 answer
133 views

### simplifying a product of a determinant and an inverse of a (nearly) singular matrix

Given two square matrices, $A$ and $B$, I need to calculate the product $tr(A^{-1}B)\times detA$. The catch is that $A$ is singular --- more precisely, it depends on some parameter $t$, such that it's ...
• 143
4 votes
1 answer
107 views

### Algorithm about finding a combination that the sum is closest to a given number

Given a matrix $P\in \mathbb{R}^{n*k}$ (just for ease of notation, no matrix or linear algebra is actually needed; bound to $(0,1)$ if necessary), select one number from each row and compute the sum. ...
• 141
4 votes
1 answer
91 views

### Worst Case complexity of a search engine algorithm

Computer make it possible to find information in large databases. However, the results are often too large to be returned in their entirety to the user who requests them. Computer therefore sort the ...
3 votes
3 answers
8k views

### What is the Complexity of MATLAB operations

I'm trying to analyze the complexity of MATLAB code I wrote. I'm trying to figure out how much (in terms of $O$ or $\Theta$) to give functions like find, matrix <...
• 133
3 votes
2 answers
2k views

### GPU vs CPU calculation

I've been working on calculating large factorials ($N>10^9$) and I was wondering if it wasn't faster to use the GPU to run the calculations on something like openCL. What I realized however was ...
3 votes
1 answer
437 views

### Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices

I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices : Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer ...
• 153
3 votes
1 answer
203 views

### Big Theta Complexity of Gaussian Elimination using Complete Pivoting

I already know the Big O for partial pivoting is $O(n^3)$ and remain the same for complete pivoting. I also know the big theta complexity for partial pivoting is $2/3 n^3$ I would like to know the ...
• 33
3 votes
1 answer
197 views

### Examples of high polynomial order complexity

I was reading Twenty Questions for Donald Knuth and was intrigued by Knuth's argument in question 17 for why he suspects P=NP. In the discussion he asks why you couldn't have an algorithm bounded by a ...
• 133
3 votes
1 answer
3k views

the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $... • 550 3 votes 1 answer 3k views ### Time complexity of$l_2$-norm of a vector What is the complexity (in flops, floating-point operations) of taking the$l_2$-norm of vector$\mathbf{v}\in\mathbb{R}^n$(or$\mathbf{v}\in\mathbb{C}^n$if a difference exists). We have the ... 3 votes 1 answer 225 views ### What is the worst case complexity of the symmetric tridiagonal QR eigenvalue algorithm? Ignoring eigenvectors, the shifted QR algorithm for computing eigenvalues in the symmetric tridiagional case costs$O(n)$per iteration, converges globally, and converges cubically near the end. What ... • 3,959 3 votes 1 answer 3k views ### Fast nearest neighbor search, Latitude Longitude Is there a fast nearest neighbor search algorithm that generates the nearest neighbors, not based on Euclidean distances but based on geographic distances over a set of latitudes/longitudes. The fast ... • 259 3 votes 1 answer 101 views ### Improve optimization over 'mapping' of indices I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference ... • 343 3 votes 2 answers 402 views ### How to prove that my problem is np-hard For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting. The problem is that i know that this is hard to solve, but i dont know if ... • 131 3 votes 0 answers 145 views ### What is the computational cost of using complex numbers in contrast to real numbers in matrix operations, e.g.$LU$or$LDL^T\$ factorizations? [duplicate]

I am curious about how much one loses in terms of computational cost when complex numbers are used instead of real numbers? I guess the number of floating-point operations and memory doubles, but I ...
• 245