Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
46
questions
23
votes
3
answers
3k
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 ...
- 3,909
48
votes
7
answers
6k
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 ...
- 16.4k
5
votes
1
answer
1k
views
Fast algorithm for computing cofactor matrix
I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
- 53
34
votes
6
answers
33k
views
What is the fastest way to calculate the largest eigenvalue of a general matrix?
EDIT: I am testing if any eigenvalues have a magnitude of one or greater.
I need to find the largest absolute eigenvalue of a large sparse, non-symmetric matrix.
I have been using R's ...
- 511
13
votes
2
answers
3k
views
How do I find the minimum-area ellipse that encloses a set of points?
I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
- 133
11
votes
1
answer
2k
views
Sensitivity of BFGS to initial Hessian approximations
I'm trying to implement the Broyden-Fletcher-Goldfarb-Shanno method to find the minimum of a function. I need two initial guesses $x_{-1}$ & $x_0$ and an initial Hessian Matrix approximation $B_0$...
- 12k
7
votes
5
answers
12k
views
How to solve block tridiagonal matrix using Thomas algorithm
Thomas algorithm can be used to solve a tridiagonal matrix:
$$
\begin{bmatrix}
{b_ 1} & {c_ 1} & { } & { } & { 0 } \\
{a_ 2} & {b_ 2} & {c_ 2} & { } & { }...
- 345
6
votes
3
answers
5k
views
How to find QR decomposition of a rectangular matrix in overdetermined linear system solution?
While trying to find cell-centered gradients in finite volume method computation of incompressible fluid flow I get over-determined linear system. This is a well known "cell based least-square" ...
- 1,403
5
votes
2
answers
574
views
How to parallelize a banded direct solver?
I have a linear system whose matrix that is diagonally dominant, non-symmetric, but banded. Since the band-radius is 2 (producing only 5 variables per equation), a banded direct solver (gaussian ...
- 12k
4
votes
1
answer
105
views
Stochastic cellular automata - algorithm limited by 1 cell per timestep
Context
Let's say I am trying to model the spread of mold in a petri dish, using a stochastic cellular automata approach. The petri dish can be thought of as a grid of 1mm x 1mm squares, each called ...
- 197
4
votes
4
answers
8k
views
Efficient assembly of finite element matrix in MATLAB
Question
What is the most efficient algorithm for finding a row of a matrix which matches a given row? This is the same as a table lookup based on multiple criteria.
Context
Finite Element Matrices ...
- 178
3
votes
2
answers
389
views
Get equation for a curve which intersects x at seemingly randomly distributed points?
Is there any type of function that when graphed would show a curve which intersects the x axis multiple times, with each point being an arbitrary distance from the last?
I mean, not like a trig ...
- 139
3
votes
0
answers
339
views
logsumexp with one very large term and many very small terms
I want to compute an expression of the form:
$$L = \ln\sum_i e^{x_i}$$
Suppose that there are many small terms, say $e^{x_i} \approx \epsilon$. If there are $N_\epsilon$ such terms, their ...
- 1,729
0
votes
1
answer
896
views
Trouble Implementing 1d Wave Equation Finite Difference Solver
Im trying to solve the 1d Wave Equation on $x \in \mathbb{R}, t > 0$: $$u_{tt} = c^2u_{xx}, \hspace{5mm} u(x,0) = \cos(4 \pi x), \hspace{5mm} u_t(x,0) = 0$$ with $c = 1$ and a periodic boundary ...
- 123
0
votes
2
answers
239
views
Adaptive numerical integration of a univariate vector integrand
Background & Problem formulation
I'm trying to write a simple program in C++ that performs adaptive numerical integration of vector valued integrands (in one variable), i.e.
$$\int_a^b \bar{f}(...
- 101
21
votes
2
answers
2k
views
Algorithms for a many-to-many generalized assignment problem
I can't seem to find any literature on algorithms which can be used to solve a many-to-many generalized assignment problem (GAP), i.e. models where not only can more tasks be assigned to one agent, ...
- 311
17
votes
2
answers
2k
views
(how to) write simulations that run faster?
I have started using python as the programming language for doing all my assignments in CFD. I have a very little experience in programming. I am from mechanical engineering background and am pursuing ...
- 1,480
13
votes
5
answers
1k
views
Repeated nearest neighbor calculation for millions of data points too slow
I have a dataset running into millions of data points in 3D. For the calculation I am doing, I need to calculate neighbor (range search) to each data point in a radius, try to fit a function, ...
11
votes
1
answer
1k
views
Numerical methods for inverting integral transforms?
I'm trying to numerically invert the following integral transform:
$$F(y) = \int_{0}^{\infty} y\exp{\left[-\frac{1}{2}(y^2 + x^2)\right]} I_0\left(xy\right)f(x)\;\mathrm{d}x$$
So for a given $F(y)$ ...
- 331
11
votes
2
answers
7k
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 ...
- 12k
11
votes
1
answer
2k
views
Sort a cloud of points with respect to an unstructured mesh of hexahedral cells
Question
How would you sort a cloud of points with respect to an unstructured mesh of hexahedral cells?
Each cell has a centre and a unique label to represent it. There are two cloud points ...
- 1,916
10
votes
2
answers
3k
views
Find all the roots of a function in a given interval
I need to find all the roots of a scalar function in a given interval. The function may have discontinuities. The algorithm can have a precision of ε (e.g. it is ok if the algorithm doesn't find two ...
- 201
8
votes
1
answer
634
views
Accurate and efficient computation of the inverse Langevin function
The Langevin function $\mathcal{L}(x) = \mathrm{coth}(x) - \frac{1}{x}$ occurs in computations related to elastomers and paramagnetic materials. It is easily computed accurately and with high ...
- 1,855
8
votes
1
answer
314
views
Compute eigenvectors of a matrix with known eigenvalue spectrum
If I have already accurately known the eigenvalue spectrum (i.e. all eigenvalues) of a matrix, is there any efficient numerical algorithm to compute all the eigenvectors corresponding to these ...
8
votes
2
answers
4k
views
Proper data-structure and algorithm for 3-D Delaunay triangulation
I have worked out some poor code to achieve the goal of 3D Delauney triangulation(random points in E3), but the time consuming is huge, and when five points are exactly (or nearly due to the round-off ...
- 81
7
votes
4
answers
884
views
When analyzing a parallel algorithm, how do you take communication costs into account?
My question is related in spirit to "Is algorithmic analysis by flop counting obsolete?". Counting the number of computational operations in an algorithm is commonly used as a first-order model to ...
- 30.3k
7
votes
1
answer
1k
views
Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix
Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix.
For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
- 189
7
votes
6
answers
9k
views
Python implementations of Gillespie's direct method
I'm looking for a decent implementation of Gillespie's Direct Method in Python, as if I code the algorithm myself I'm nigh positive I'll do it inefficiently.
Anyone have a favorite?
- 2,383
6
votes
3
answers
7k
views
Algorithm for Principal Eigenvector of a Real Symmetric 3x3 Matrix
I have a 3x3 covariance matrix (so, real, symmetric, dense, 3x3), I would like it's principal eigenvector, and speed is a concern. Is there a fast algorithm for this specific problem? I've seen ...
- 203
6
votes
2
answers
337
views
Is it possible to ignore/discard part of a matrix when finding eigenvalues?
I have have multiple large matrices for which I need to find the largest absolute eigenvalue. I know that there is a large submatrix that does not vary. Is it possible to ignore/discard the submatrix?
...
- 511
6
votes
1
answer
647
views
Eigenvector with maximum overlap
Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
- 243
6
votes
1
answer
393
views
What efficient algorithms are there to generate arbitrary dimensional meshes of simplices?
I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh ...
- 12k
5
votes
2
answers
255
views
Is there a special algorithm for computing the convex hull ordering when the candidate points are on the hull?
I'm dealing with a set of points which are already placed on the 2D hull boundary: a convex polygon. I know this for sure. However, the point set is not ordered, and I need the polygon points to be ...
- 1,916
5
votes
3
answers
186
views
Algorithms for radiation treatment planning
I have a medical physics problem - I want to maximise the dose absorbed by a brain tumour whilst minimising the dose in the rest of the brain, especially certain organs, such as the pituitary gland, ...
5
votes
3
answers
232
views
Is there a way to reduce aberration in computations of planets' trajectories?
I don't think the title is very accurate , sorry for that.
I simulate bodies in space using two timestep:
the TIMESTEP is the Δt wich I use to make the calculation
and XTIME is the number of times ...
- 151
4
votes
1
answer
257
views
constrained minimization in N dimensions
I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions
Minimize $ \sum_{i} x_i\left [ f\...
- 173
4
votes
3
answers
276
views
Algorithms to generate spherical codes
A spherical code, specified by the parameters $(n,N,t)$, is a set of $N$ coordinates on the $n$-dimensional unit hypersphere such that the set of dot products between any two unit vectors from the ...
- 229
4
votes
3
answers
7k
views
How to get ODE solution at specified time points?
The code below basically illustrates my problem. It is a test code for a pendulum. I solve it using a method suggested on https://stackoverflow.com/questions/12926393/using-adaptive-step-sizes-with-...
- 873
3
votes
1
answer
374
views
Evaluate 3D Shape Descriptor
I'm trying to create my own 3d shape descriptor, the idea is that how I may evaluate how much my descriptor is well and good?
What I checked is that they evaluate descriptors through shape matching, ...
- 43
3
votes
2
answers
4k
views
C++ Library: What is the common libraries that do polynomial arithmetic?
I need to know what libraries (in C++) support polynomial arithmetic specially over a field. So I can give to it an array of coefficients of polynomial over a field and it returns the roots of ...
- 161
3
votes
2
answers
272
views
Generate Random Number outside Bounds:
Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.
How do I ...
- 143
3
votes
1
answer
3k
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 ...
- 259
2
votes
2
answers
631
views
Effective way to build the neighbor's list in MD
I'm trying to implement the following form of the cell/neighbor list method in my MD code. I have divided my simulation box into a fixed number of cells, and according to its positions, I have ...
- 187
1
vote
3
answers
2k
views
Algorithm to compute the intersection of two lines given their cartesian equations
I'm looking for a way to compute the coordinates of the intersection of two lines.
Each lines are defined with a point and a normal vector.
We can assume than the normal vectors are not zero and ...
- 113
1
vote
2
answers
100
views
Maintain Uniform Distribution across Subranges
Note: this is a continuation of Generate Random Number outside Bounds.
I have a function (thanks to the previous question) with the following prototype which returns an integer in the range $[0,b]$, $...
- 143
0
votes
1
answer
222
views
Fast chain rule algorithm [closed]
Assume I have two functions $f$ and $g$, with derivatives of $g$ at point $x$ and derivatives of $f$ at point $g(x)$ available.
What is the fastest way of computing derivatives of $f \circ g (x)$ ?
- 103