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

learn more… | top users | synonyms

3
votes
0answers
72 views

Efficient algorithm for a matrix porduct

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
0answers
34 views

Compute an orthonormal bases for a full column rank matrix

Recall that given a full column rank matrix $A\in\mathbb{R}^{n\times k}$, we have discussed a reliable algorithm to compute an orthonormal basis of $\mathcal{R}(A)$ by computing the Household ...
3
votes
1answer
104 views

Determine a sufficient condition for a Hessenberg matrix to be nonsingular

Consider $A\in\mathbb{R}^{n\times n}$ whose nonzero elements are restricted to the main diagonal the strict upper triangular part, and the first subdiagonal. For $n = 8$ the locations that must be ...
0
votes
1answer
44 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 &...
0
votes
0answers
18 views

Determine an algorithm for $LU$ factorization and determine the number of operations

Suppose that $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^{T}A^{-1}e_j$, i.e., the $(i,j)$ elements of $A^{...
2
votes
2answers
87 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
58 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 ...
0
votes
1answer
49 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
16 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
53 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.
1
vote
1answer
43 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
23 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 ...
14
votes
3answers
356 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
0answers
69 views

Computational complexity for generating this matrix?

There is a $m\times n$ non-symmetric Toeplitz matrix $T$ generated using a deterministic function $f$ and the relationship is $x(n) = f(x(n-1))$. For example, $f(x) = 4x(1-x)$ A single sequence $x$ ...
0
votes
1answer
78 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
96 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
161 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
301 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
159 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
31 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
25 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 ...
1
vote
0answers
47 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
92 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
111 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
182 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
86 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
235 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
73 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
137 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
741 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
138 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
110 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 ...
3
votes
2answers
296 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
90 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.
6
votes
4answers
4k 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 ...
1
vote
1answer
74 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
269 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
99 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
313 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 matrix,...
2
votes
1answer
921 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 ...
12
votes
2answers
497 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
5k 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
120 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} − \sum_{i=1}^...
4
votes
1answer
111 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
52 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
159 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
95 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
73 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
318 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
637 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 ...