# Questions tagged [complexity]

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

89 questions
Filter by
Sorted by
Tagged with
130 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 ...
65 views

### Flops of the computation of symmetric matrix $A$ to the power of $p$

What is the cost in terms of flops for the computation of $A$ to the power of $p$, where $p$ is a positive integer and $A \in \mathbb R^{n\times n}$ is a symmetric matrix?
101 views

### Time complexity of numerical finite differences

I have a function $f:\mathbb R^N\to \mathbb R$ and I would like to compute all the partial derivatives of $f$ w.r.t. the $N$ input. What is the computational complexity using the (ones-sided) finite ...
54 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 ...
69 views

### What is an instance (precisely) in computational complexity?

I am trying to understand the notion of reduction of a problem to another problem. As it is known this has huge impact on classifying the complexity of a problem. The definition of reduction involves ...
78 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 ...
138 views

### Efficient CRS vectors evaluation using elements connectivities

What is an efficient way of evaluating the column (col_ind) and the row (row_ptr) vectors for the CRS (Compressed Row Storage) storage format using the Connectivity Array? The Connectivity Array is a ...
147 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 ...
49 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 ...
16 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-...
192 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?
394 views

221 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 ...
97 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 ...
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 ...
191 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 ...
90 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 &...
132 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$ ...
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 ...
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 ...
44 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 ...
83 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.
193 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 ...
158 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 ...
515 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 ...
206 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 ...
586 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 ...
366 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{...
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 ...
409 views