Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [algorithms]

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

35 questions
Filter by
Sorted by
Tagged with
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 ...
5k 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 ...
21k 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 ...
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 ...
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$...
464 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 ...
135 views

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, ...
710 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, ...
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 ...
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 ...
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 ...
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 ...
313 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 ...
223 views

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\... 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 ... 1answer 848 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)$... 2answers 245 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? ... 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, ... 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 ... 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 ... 2answers 187 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 ... 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 ... 2answers 144 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 ... 2answers 74 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]$,$...
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)$ ?