# Questions tagged [algorithms]

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

459 questions
Filter by
Sorted by
Tagged with
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 ...
4k 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?
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 ...
3k 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 ...
5k 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? ...
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 ...
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, ...
938 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 ...
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 ...
288 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,...
536 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 ...
321 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 ...
256 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. ...
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 ...
689 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 ...
680 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, ...
1k 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 ...
417 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 ...
972 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/...
436 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 ...
339 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 "...
6k 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 ...
424 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 ...
325 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$, ...
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 ...
833 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)$ ...
277 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 ...
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 ...
795 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)$?
2k 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 ...
769 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 ...
2k 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 ...
2k 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$...
26k 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. ...
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

### 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$...
289 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 ...
1k 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)$. ...
925 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 ...
107 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 ...
119 views

### Estimate Norm of a black-box functional

Let $V$ be a finite-dimensional vector space with norm $\|\cdot\|$ and let $F : V \rightarrow \mathbb R$ be a bounded linear functional. It is only given as black-box. I would like to estimate the ...
400 views

### Computing the characteristic polynomial of real sparse matrix

Given a generic sparse matrix $A \in \mathbb{R}^{n\times n}$ with m << n (correction: $m \ll n^2$) non-zero elements (typically $m \in {\cal O}(n)$). $A$ is generic in the sense that it has no ...
8k 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 ...
7k 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 ...
1k views

### Newton iteration for cube root without division

It's a fairly well known trick to avoid division in calculating square-roots to apply Newton's method to finding $1/\sqrt{x}$, and probably better known, using Newton's method to find reciprocals ...
446 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 ...
3k views

### What algorithm to use for parallel dense matrix inversion on at most 8 cores?

I need to implement parallel dense matrix inversion for a language I am using that appears to not have an existing library for this (specifically IDL using IDL Bridge for message passing). I am ...
given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following ...