# Questions tagged [algorithms]

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

38 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 ...
353 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 ...
26k 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 ...
10k views

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" ...
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 ...
220 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 ...
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 ...
7k 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?
697 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 ...
331 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 ...
229 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 ...
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, ...
823 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, ...
6k 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 ...
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 ...
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 ...
3k 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 ...
329 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 ...
239 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 79 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, ... 1answer 955 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 266 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 216 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 ... 2answers 204 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 ... 3answers 180 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 6k 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 3k 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 160 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 82 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)$ ?