Questions tagged [algorithms]

A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.

20
votes
3answers
2k 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 ...
43
votes
7answers
4k 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 ...
3
votes
0answers
188 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 ...
27
votes
7answers
20k 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 ...
4
votes
4answers
7k 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 ...
5
votes
2answers
461 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 ...
6
votes
3answers
4k 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" ...
3
votes
2answers
386 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 ...
15
votes
2answers
1k 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 ...
7
votes
4answers
576 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 ...
7
votes
6answers
6k 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?
6
votes
1answer
230 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 ...
4
votes
5answers
9k 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} & { } & { }...
20
votes
2answers
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, ...
14
votes
5answers
669 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
2answers
5k 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 ...
11
votes
1answer
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 ...
9
votes
1answer
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$...
9
votes
2answers
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 ...
8
votes
2answers
2k 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 ...
5
votes
1answer
308 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 ...
4
votes
1answer
220 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\...
3
votes
1answer
2k 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 ...
11
votes
1answer
827 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)$ ...
6
votes
2answers
238 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? ...
5
votes
3answers
213 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 ...
5
votes
3answers
174 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, ...
4
votes
2answers
178 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 ...
4
votes
3answers
5k 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 ...
3
votes
2answers
2k 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 ...
3
votes
2answers
141 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 ...
1
vote
2answers
70 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]$, $...
0
votes
2answers
97 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 ...
0
votes
1answer
141 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)$ ?