Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
562
questions
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
33
votes
6
answers
32k
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 ...
- 501
28
votes
6
answers
6k
views
How can the gravitational n-body problem be solved in parallel?
How can the gravitational n-body problem be solved numerically in parallel?
Is precision-complexity tradeoff possible?
How does precision influence the quality of the model?
- 383
26
votes
10
answers
9k
views
Which algorithm is more accurate for computing the sum of a sorted array of numbers?
Given is an increasing finite sequence of positive numbers $z_{1} ,z_{2},.....z_{n}$. Which of the following two algorithms is better for computing the sum of the numbers?
...
- 395
25
votes
4
answers
43k
views
The easiest way to find intersection of two intervals
Right now I stuck with a problem. It seems to be really trivial one, but still it is hard for me to find an appropriate solution. The problem is:
One has two intervals and are to find the intersection ...
- 383
25
votes
1
answer
1k
views
Is there a numerical algorithm for finding an asymptotic slope?
I have a series of data points $(x_i,y_i)$ which I expect to (approximately) follow a function $y(x)$ that asymptotes to a line at large $x$. Essentially, $f(x) \equiv y(x) - (ax + b)$ approaches zero ...
- 3,343
24
votes
4
answers
4k
views
Algorithms for (adaptive?) function plotting
I am looking for algorithms to draw standard 2d-graphs for functions that may or may not have singularities. The purpose is to write a "Mini-CAS", so I have no a priori knowledge of the types of ...
- 345
23
votes
3
answers
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 ...
- 3,889
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
20
votes
7
answers
1k
views
How do I write dimensionally agnostic code?
I often find myself writing very similar code for one, two, and three dimensional versions of a given operation/algorithm. Maintaining all of these versions can become tedious. Simple code ...
- 2,056
19
votes
2
answers
5k
views
Numerically stable way of computing angles between vectors
When applying the classical formula for the angle between two vectors:
$$\alpha = \arccos \frac{\mathbf{v_1} \cdot \mathbf{v_2}}{\|\mathbf{v_1}\| \|\mathbf{v_2}\|}$$
one finds that, for very small/...
- 1,155
19
votes
4
answers
4k
views
Is Fortuna or Mersenne Twister preferable as an algorithmic RNG?
A recent answer mentioned the use of Fortuna or Mersenne Twister Random Number Generators (RNGs) to seed a Monte Carlo simulation. I hadn't heard of Fortuna before so I looked it up - looks like it is ...
- 658
18
votes
3
answers
389
views
What programming strategies can I take for easily modifying algorithm parameters?
Developing scientific algorithms is a highly iterative process often involving changing lots of parameters that I will want to vary either as part of my experimental design or as part of tweaking ...
- 289
18
votes
2
answers
322
views
Is there an efficient algorithm for matrix-valued continued fractions?
Suppose I have a matrix equation recursively defined as
A[n] = inverse([1 - b[n]A[n+1]]) * a[n]
Then the equation for A[1] looks similar to a continued fraction,...
- 487
18
votes
1
answer
748
views
Why are Octrees used for Multipole space decomposition?
In most (all?) implementations of the Fast Multipole Method (FMM), octrees are used to decompose the relevant domain. Theoretically, octrees provide a simple volumetric bound, which is useful for ...
- 476
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
17
votes
3
answers
294
views
Uses of power series maps
I'm from the field of accelerator physics, specifically related to circular storage rings for synchrotron light sources. High energy electrons circulate around the ring, guided by magnetic fields. ...
- 171
15
votes
1
answer
758
views
Are there any open source inverse-based multilevel ILU implementations?
I am very impressed with the serial performance of multilevel inverse-based ILU preconditioners, particularly for heterogeneous Helmholtz, but I am surprised to not be able to find any open source ...
- 7,589
14
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, ...
14
votes
2
answers
43k
views
What is the fastest algorithm for computing the inverse matrix and its determinant for positive definite symmetric matrices?
Given a positive definite symmetric matrix, what is the fastest algorithm for computing the inverse matrix and its determinant? For problems I am interested in, the matrix dimension is 30 or less.
...
- 283
14
votes
1
answer
3k
views
What are the relative benefits of using Adams-Moulton over Adams-Bashforth algorithm?
I am solving a system of two coupled PDE's in two spatial dimensions and in time computationally. Since the function evaluations are expensive, I would like to use a multistep method (initialised ...
- 311
13
votes
5
answers
493
views
What are the benefits and drawbacks inherent to using classes to encapsulate numerical algorithms?
Many algorithms used in scientific computing have a different inherent structure than algorithms commonly considered in less math-intensive forms of software engineering. In particular, individual ...
- 1,483
12
votes
6
answers
9k
views
How do compression algorithms compress data so fast?
I've come across compression algorithms, I tried creating a simple run-length encoding algorithm but I notice that when I searched other algorithms I was shocked to know that some algorithms can ...
- 153
12
votes
2
answers
2k
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 ...
- 123
12
votes
2
answers
652
views
Computation of Cholesky factor
So the Cholesky decomposition theorem states that
that any real symmetric positive-definite matrix $M$ has a Cholesky decomposition $M= LL^\top$ where $L$ is a lower triangular matrix.
Given $M$, ...
- 645
12
votes
1
answer
532
views
Algorithms for Large Sparse Integer Matrices
I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
- 123
12
votes
1
answer
369
views
Enumeration of graphs deriving from Delaunay tessellations in 3D
Is there an algorithm that enumerates the graphs that correspond to some Delaunay tessellation of points in 3D?
If so, is there an efficient parameterization of geometries that correspond to any "...
- 1,042
11
votes
3
answers
7k
views
I am looking for a parallel dynamic graph library in C++
Hello scicomp community,
I have worked in the area of graph algorithms using frameworks such as NetworkX (Python), JUNG and YFiles (Java). I am now entering the area of parallel and high perfomance ...
- 243
11
votes
2
answers
3k
views
What's the most efficient way to compute the eigenvector of a dense matrix corresponding to the eigenvalue of largest magnitude?
I have a dense real symmetric square matrix. The dimension is about 1000x1000.
I need to compute the first principal component and wonder what the best algorithm to do this might be.
It seems that ...
- 211
11
votes
4
answers
514
views
Should benchmarkings be done at all? What is the point?
I am reading a paper which compares algorithm A versus algorithm B.
It shows that algorithm A is faster than algorithm B via benchmarking that shows the CPU time.
What is the point of this? Any ...
- 111
11
votes
3
answers
518
views
Parallel algorithm for eigensystem of a tridiagonal matrix
I'm doing a Lanczos diagonalization of a large sparse matrix (~2 million elements). Almost all of the steps in the Lanzcos algorithm are done in parallel on the GPU, except for diagonalizing the ...
- 405
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 ...
- 11.9k
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
3
answers
877
views
Complex numerical analysis
What numerical analysis situations become more/less stable, have faster/slower convergence, or are otherwise quite different when dealing with functions of complex variable instead of functions of a ...
- 367
11
votes
3
answers
3k
views
Volume of 3D convex hull of small point sets all on the hull
I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull.
More precisely, I'm given a small set of points (say, 10-15) in ...
- 4,460
11
votes
2
answers
3k
views
computing the truncated SVD, one singular value/vector at a time
Is there a truncated SVD algorithm that computes the singular values one at a time?
My problem: I would like to compute the first $k$ singular values (and singular vectors) of a large dense matrix $M$...
- 213
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$...
- 11.9k
11
votes
3
answers
311
views
How to implement efficient indexing function for two particle integrals <ij|kl>?
This is a simple symmetry enumeration problem. I give the full background here, but no knowledge of quantum chemistry is needed.
The two particle integral $\langle ij|kl\rangle$ is:
$$
\langle ...
- 2,920
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
3
answers
864
views
Is there a complexity between $O(n)$ and $O(n \log n)$ [closed]
Is there a complexity degree that is bigger than $O(n)$ and smaller than $O(n \log n)$?
- 101
10
votes
2
answers
17k
views
Dictionaries in pseudocode
What is a good, common way to express dictionaries (= maps) in pseudocode? I.e. datastructures that basically allow to store values for keys, iterate over all key/value pairs, test for inclusion of a ...
- 203
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
10
votes
2
answers
2k
views
Is there an algorithm to find an almost-convex hull given a tolerance angle?
I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows ...
- 203
9
votes
2
answers
2k
views
Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?
I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
9
votes
2
answers
3k
views
Markov (Chain) image generators?
Markov Chains can be used to generate, or auto-complete, text.
https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators
Training text is read, and some information about the text is ...
- 193
9
votes
1
answer
1k
views
N-body simulation optimisation, looking for name or existing work
during the development of my N-body simulation with visualisation in WebGL, I devised an optimisation, and I'm wondering if it has a name. I find it unlikely that it has never been done before.
It ...
- 243
9
votes
2
answers
389
views
How does weak convergence feel, numerically?
Consider, you have a problem in an infinite dimensional Hilbert or Banach space (think of a PDE or an optimization problem in such a space) and you have an algorithm that converges weakly to a ...
- 1,738
9
votes
2
answers
2k
views
How to generate neighbors in hill climbing algorithm?
Hill climbing seems to be a very powerful tool for optimization. However, how to generate the "neighbors" of a solution always puzzles me.
For example, I am optimizing a solution $(x_1, x_2, x_3)$. ...
- 373
9
votes
1
answer
235
views
Is there a way we can compute my sum involving `subsets` more efficiently?
Suppose we have a countably infinite $A$ and $F_1,F_2,\cdot\cdot\cdot$ are an infinite sequence of finite sets (denoted $\left\{F_n\right\}_{n=1}^{\infty}$) such that $\bigcup\limits_{n=1}^{\infty}F_n=...
- 53
9
votes
1
answer
136
views
Numerically stable algorithms for computing remainder of polynomials
Let $f, g \in \mathbb{R}[x]$ and $\deg f > \deg g$. I am looking for asymptotically fast and numerically stable algorithms for computing $f \bmod g$. In the applications intended, both $f, g$ are ...
user182