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

learn more… | top users | synonyms

0
votes
0answers
23 views

How to measure the computational costs of solving CSPs and optimization problems?

I would like to define an abstract cost (machine and implementation independent measure) of the work needed to solve CSPs as a function of constraint and Jacobian evaluation counts. I am trying to ...
2
votes
2answers
113 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) ...
0
votes
0answers
22 views

I can't access to my account [duplicate]

exactly very bizarre.... I can't access to my account How do you think it could be possible to compute this relation and to find prime numbers. The question is related of the good algorithm, time, ...
2
votes
1answer
73 views

Optimal algoritm of gcd with complexity

I want to know the best optimal algoritm of gcd with its complexity if you have a any useful source I will be glad to have a look at it.
4
votes
2answers
145 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 ...
0
votes
0answers
17 views

Algorithmic complexity of dimension estimation algorithms

I am looking for resources which mention the space - time complexities of different algorithms used to compute the fractal dimension for instance, the Grassberger's Correlation dimension, Floris ...
1
vote
1answer
66 views

How to interpret Turing Machine illustrations on p79 of Stephen Wolfram's “A New Kind of Science” book?

I am reading Stephen Wolfram's "A New Kind of Science". At present, I cannot understand how the cellular automata illustrations on p79 are created. In the patterns, the active cell, representing the ...
9
votes
2answers
198 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 ...
6
votes
1answer
91 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 ...
9
votes
5answers
219 views

How to deal with complexity in numerical code, for example, when dealing with large Jacobian matrices?

I am solving a non-linear system of coupled equations, and have calculated the Jacobian of the discretised system. The result is really complicated, below are (only!) the first 3 columns of 3x9 ...
2
votes
1answer
197 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 ...
8
votes
1answer
235 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 ...
3
votes
3answers
1k 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 ...
1
vote
1answer
92 views

How to calculate the complexity of a given Algorithm

I have the following algorithm given: Input: Regular Matrix $A \in \mathbb R^{n,n}$ Output: LU-Decomposition of A = LU for k = 1, . . . , n do for j = k, . . . , n do $r_{kj} = a_{kj} − ...
4
votes
1answer
96 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 ...
2
votes
2answers
50 views

Clustering Algorithm for a congruence relation?

Say we are given a congruence relation$~\sim$ in a dataset with $n$ elements. I am looking for an algorithm for optimally sorting the $n$ elements into $m$ clusters according to given congruence ...
5
votes
2answers
129 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 ...
2
votes
2answers
84 views

How does an automaton actually “compute”?

In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary ...
3
votes
1answer
65 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 ...
5
votes
1answer
176 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 ...
2
votes
2answers
319 views

Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be-as in - Is ...
5
votes
1answer
46 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: ...
4
votes
2answers
238 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, ...
3
votes
2answers
132 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 ...
3
votes
1answer
82 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 ...
2
votes
0answers
41 views

Complexity of direct solvers? [duplicate]

Possible Duplicate: How to reorder variables to produce a banded matrix of minimum bandwidth? What is the time and space complexity of direct sparse solvers (e.g., UMFPACK, SUPERLU, ...
5
votes
1answer
367 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 ...
7
votes
2answers
772 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 ...
4
votes
2answers
919 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$, ...
5
votes
1answer
108 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: ...
6
votes
0answers
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 ...
9
votes
4answers
2k 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 ...
2
votes
2answers
263 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 ...
1
vote
3answers
567 views

Computational Complexity of Image Segmentation algorithms

I have a question. I need to calculate the computational complexity of image segmentation algorithms. Can anyone please help me? For example, I have a screen-size picture with white background ...
13
votes
3answers
520 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 ...
16
votes
5answers
1k 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?
32
votes
7answers
1k 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 ...
12
votes
1answer
206 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 ...