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
22
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 ...
46
votes
7answers
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 ...
5
votes
1answer
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 ...
28
votes
7answers
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 ...
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 ...
6
votes
5answers
10k 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} & { } & { }...
10
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$...
5
votes
2answers
476 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 ...
0
votes
2answers
145 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}(...
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 ...
3
votes
0answers
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 ...
16
votes
2answers
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 ...
7
votes
6answers
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?
7
votes
4answers
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 ...
6
votes
1answer
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 ...
8
votes
1answer
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 ...
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
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, ...
11
votes
2answers
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 ...
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
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
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 ...
6
votes
1answer
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 ...
4
votes
1answer
239 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 ...
3
votes
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, ...
11
votes
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)$ ...
7
votes
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?
...
5
votes
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 ...
5
votes
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 ...
5
votes
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, ...
5
votes
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 ...
4
votes
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 ...
3
votes
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 ...
1
vote
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]$, $...
1
vote
2answers
225 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
177 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)$ ?
