# Tagged Questions

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

73 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 ...
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 ...
106 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 ...
45 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 &...
18 views

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 ...
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 ...
47 views

189 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 ...
88 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) ...
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 ...
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 ...
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 ...
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)$?
140 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 ...
111 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 ...
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) ...
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.
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 ...
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 ...
270 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 ...
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 ...
314 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,...
944 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 ...
505 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 ...
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 <...
121 views