Questions tagged [complexity]

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

0
votes
0answers
82 views

Calculate amount of FLOPs for an eigenvalue problem solver

I have 2 complex, non-symmetric, matrices $A_{1000\times1000}$, $B_{1000\times1000}$ and I am using Matlab to get it's eigenvalues (functions like eig or eigs). Both matrices are different - one is ...
2
votes
1answer
41 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 ...
0
votes
0answers
13 views

Cost functions to judge time/memory/accuracy tradeoffs

I am working on an interesting algorithm: Its absolute error is exponential in a parameter $j \in \mathbb{N}$, and for a given $j$, I have complete freedom to choose between an $\mathcal{O}(1)$ time-...
2
votes
2answers
114 views

Asymptotic Complexity of Gaussian Elimination using Complete Pivoting

I would like to know the algorithm asymptotic complexity with Complete Pivoting. With partial pivoting, it is known to be $O(n^3)$. Is it the same for complete pivoting?
3
votes
1answer
193 views

Computational complexity of Newton's method

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 $...
7
votes
2answers
140 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 ...
2
votes
1answer
76 views

Convergence rate and complexity for convex minimization problem

In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization ...
1
vote
1answer
88 views

System of ordinary differential equations - time complexity of initial value problem

I am interested in knowing what the time complexity is (in Big-$\mathcal O$ notation) for solving system of $N$ differential equations? I am using ode15s in ...
2
votes
1answer
266 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
1answer
359 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: ...
0
votes
1answer
97 views

finding the growth rate from numerical data

Suppose i have a bunch of 10 data points and i have to conclude whether the increase is $n^2,n^3,\cdots,2^n,3^n, e^n,\cdots$. For example i have the image:- Now the increase is either polynomial or ...
2
votes
2answers
62 views

Efficient Representation of (spatially sparse) spatial time series

Background I have a huge dataset consisting of points (on a plane) together with a timestamp for each point. This is a collection of car GPS measures, giving us the location (latitude/longitude) of ...
4
votes
0answers
309 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 ...
2
votes
1answer
119 views

Regarding impractical usage of direct solvers of linear systems [closed]

Since the computational complexity of direct elimilation methods for solving linear systems is $O(n^3)$, it's not practical when the number of dofs is large. But how large would you call it a large ...
1
vote
1answer
107 views

Big-O Complexity of Gini Index

What will be the complexity of finding Gini Index of a sorted vector of $N$ values, which is defined as: $Gini(\mathbf{x})=1-2\sum_{k=1}^N \frac{\mathbf{x}(k)}{\Vert\mathbf{x}\Vert_1}(\frac{N-k+.5}{N}...
1
vote
0answers
188 views

Generalization error and Sample Complexity estimation for Least Squares

I am wondering how to draw a sample complexity plot similar to the following figure which shows the estimated number of samples to incur no more than 10 percent generalisation error on average for the ...
2
votes
0answers
96 views

Is the numerical resolution of this huge sparse polynomial system tractable?

I'd like to find numerically a solution to a sparse system of 2000000 polynomial equations of degree 3 with 50000 variables and integer coefficients (or at least to decide whether or not a solution ...
1
vote
2answers
95 views

What is meant by “operations”?

In this paper, on page 243, we have $$d_{jk} = \frac{a_j}{a_k(x_j - x_k)}$$ where $$a_k = \prod_{l = 0;l\neq k}^{N}(x_k-x_l)$$ Now, $a_k$ requires evaluating N multiplications. Why does the author ...
2
votes
1answer
175 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 ...
0
votes
1answer
82 views

$LU$ Factorization of a nonsingular matrix with a particular pattern

Consider $S\in\mathbb{R}^{n\times n}$ whose nonzero elements have the following pattern for $n = 8$: $$\begin{pmatrix} 1 & 0 & 0 & 0 & \mu_1 & 0 & 0 & 0\\ 0 & 1 &...
2
votes
2answers
116 views

What kind of optimisation algorithm is suitable for a computationally expensive function?

I have a reference value $R$ and a modelled value $M$. $M$ is generated using a stochastic algorithm with parameters $a$ and $b$. The objective is to tune $a$ and $b$ so that $M$ is as close as $R$ ...
0
votes
1answer
185 views

Notations for algorithmic complexity in elementary operations

I am comparing several algorithms (moments and matrix products) for real-time computing in terms of numerical complexity in elementary operations. [EDIT] Algorithms are very similar in terms of ...
1
vote
1answer
92 views

Expected runtime complexity of repeated closest Point Pair search

I have to vectors $X_1$ and $X_2$ with 3 dimensional points $p_i$ and $p_j$ contained. As long as $X_1$ is not empty, I want to find the closest pair $p_i$ and $p_j$. The point $p_i$ of this pair I ...
1
vote
0answers
39 views

I'm using linear programming for production planning. Does the order in which I make products affect the cost?

I have a collection of different scrap aluminium alloys. I want to mix them together to make new alloys with customer-defined compositions. Sometimes this will involve little more than melting down ...
1
vote
1answer
81 views

computational complexity for computing perimeter of a polygon

What is computational complexity for computing perimeter of a polygon of $n$ vertices? The polygon is not necessarily regular and can be convex or non-convex.
2
votes
1answer
191 views

Probability of reconstructing a word using c substrings from a random sample

Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to ...
0
votes
1answer
119 views

Single Precision a x plus y (SAXPY) terminology

I've been reading books which refers to vector update operations of the form: y := y + ax, where y and x are vector variables and a is a scalar as SAXPY. I understand ax plus y part, but why "single ...
15
votes
3answers
466 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 ...
0
votes
1answer
180 views

Mathematical Complexity of Sparse Solvers

For a system $\mathbf{x=Da}$, there exist a lot of algorithms to estimate sparse vector $\mathbf{a}$. I wish to know the big-O mathematical complexity of 1) orthogonal matching pursuit (OMP) both ...
8
votes
1answer
435 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 ...
0
votes
1answer
305 views

Storage complexity of SDP solver SCS

This is a follow up question to this question. Consider the following SDP in standard form: \begin{align} &\min_{X\in S^n, X>0} \operatorname{tr}(AX)\\ &\mbox{subject to}\; \operatorname{...
2
votes
2answers
1k 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 ...
2
votes
1answer
335 views

Comparison of convex hulls [closed]

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,......
1
vote
1answer
34 views

When we compute the complexity of a given algorithm related to image processing does the N refers to the number of Pixels in the image?

When we compute the complexity of an image processing algorithm, we get an $O(N)$. does the $N$ refers to the number of pixels in the image or to the height/width of the image, I mean it is computed ...
1
vote
1answer
30 views

Computational complexity of chemical dynamics for biological studies [closed]

How many CPU cycle is required to simulate a complete human body from it's very initial stem cell using classical algorithms and also is it possible to use similar algorithms for simulating stem cells ...
2
votes
0answers
67 views

How to determine the minimum number of multiplication needed for a specific expression?

Is there any algorithm to determine the minimum number of multiplication(division) of a specific expression? and the optimal expression form for implementation? For example, given values of $\cos\...
0
votes
1answer
271 views

Comparing computational complexity of convex optimization and a heuristic algorithm

I am working on a resource allocation problem, which is convex and has several constraints, and I want to compare the computational complexity of the following algorithms. 1) The algorithm that uses ...
1
vote
2answers
145 views

How to prove time complexity of merge sort

I was asked to prove that the time complexity of merge sort is $ O(log_2n)$ but I cannot find a way to continue my method. Any help? $T(n)=2T(\frac{n}{2} )+n$ $T(n)= 2[2T(\frac{n}{4})+n] +n = 4T(\...
1
vote
2answers
910 views

Time complexity for sparse direct solver for SPD system with respect to number of equations, bandwidth, number of nonzeros?

I am looking for information on the time complexity for solving sparse system Ax=b with direct solver. This system results from a finite-element discretization of an elliptic problem. The matrix A ...
0
votes
1answer
114 views

Help me analyze the computational cost of two kinds of operations

everyone, I have a question about computational costs for a algorithm. That is: I have two vectors $u_n,\ v_n\in \mathbb{C}^N$, a matrix $A\in \mathbb{C}^{N\times N}$ (can be both sparse and dense) ...
8
votes
1answer
244 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 ...
0
votes
1answer
76 views

difference of polytopes in $\mathbb{R}^n$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard? $p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \} $ // CH is convex hull computed on union of a polynomial ...
5
votes
2answers
175 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 ...
10
votes
3answers
794 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)$?
3
votes
1answer
178 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 ...
0
votes
2answers
380 views

How to decrease computation time for symmetric matrices?

We all know the problem that computation time explodes when simulating systems with big matrices. I got just this problem, but I have the advantage that I know that my matrices are symmetric. My ...
13
votes
3answers
3k 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 ...
3
votes
2answers
386 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) ...
2
votes
1answer
103 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.
7
votes
4answers
14k 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 ...