Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithms]

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

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
1answer
309 views

Generating a tuple in Maple

I am trying to generate a 2 tuple using maple. Can anyone give me the command to generate this? Thank you very much.
9
votes
2answers
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 ...
4
votes
1answer
69 views

How to use a web-embedded model in a computational workflow?

There is a model embedded in a web browser (Caprio 1998) that I would like to use in an MCMC algorithm. What is the best way to do this? I could implement the model in my favorite language but I ...
7
votes
3answers
326 views

Given large $x \in \mathbb{R}$, How to determine if $2^x$ is an integer?

Given large $x \in \mathbb{R}$, I want to know whether or not $2^x$ is an integer. Is there any fast way to answer the question for $x>2^{500}$? I have also asked a slightly different form of this ...
2
votes
2answers
2k views

Depth of a Binary Search Tree

I wrote a function to search a Binary Search Tree, but I have logic problems: When I insert some values, and I have a tree of 2 levels, and the final level (2 in this case) is not full (full is that ...
6
votes
2answers
228 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? ...
11
votes
2answers
4k 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 ...
19
votes
6answers
903 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 ...
11
votes
3answers
418 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 ...
26
votes
7answers
19k 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 ...
6
votes
1answer
155 views

Algorithm for generating all cartesian products, without rotations

(Not sure if that's the right SX site? I don't need actual code, so…) I'm looking for an algorithm that generates all cartesian products for a list of sets, but skips tuples that are just rotations ...
9
votes
3answers
377 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 ...
5
votes
2answers
1k views

An efficient way to numerically compute Stirling numbers of the second kind?

Is there an efficient way to numerically compute Stirling numbers of the second kind? An approximate (not exact) method would suffice. Something similar to the connection between factorials and gamma ...
5
votes
2answers
8k views

What is the difference between O(n) and o(n)? [closed]

I was studying Big-Oh notation, and there is apparently a difference between $O(n)$ and $o(n)$. What is it? I think $f(n)$ is $o(n)$ means that $$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$ but what ...
9
votes
1answer
105 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 ...
4
votes
4answers
215 views

Determining the algorithmic complexity

A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of ...
11
votes
1answer
1k 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 ...
8
votes
2answers
6k 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 ...
7
votes
1answer
533 views

Heuristic for Gibbs sampler annealing schedule

Suppose one is performing Gibbs sampling with a Boltzmann distribution (or if you prefer, simulated annealing) at finite temperature. In general we would want to anneal: as the sampler converges to ...
15
votes
1answer
679 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 ...
8
votes
2answers
267 views

One-sided non-linear least squares with linear constraints

I am trying to solve a one-sided non-linear least-squares problem with linear constraints, i.e the problem: $\min_{\mathbf{x}} \quad \sum^m_{i=1} \mathbf{r}_i(\mathbf{x}) \qquad \text{ s.t } \quad A\...
5
votes
0answers
2k views

Two-chordless cycle extraction from a failed comparability graph recognition

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
10
votes
2answers
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 ...
12
votes
1answer
335 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 "...
7
votes
4answers
2k views

precision vs matrix condition number

I have an application in which I am computing a quantity which is approximated by an average over $M$ points. In theory, the average converges to the correct quantity when $M$ is infinite. In practice,...
1
vote
0answers
80 views

Constraint solving over modular domains

I have a set of constraints over modular domains e.g. $\exists a \in A_i : x \equiv a \pmod{n_i}$ for all $i=0,\ldots,k$ The question is, does such an $x$ exist? I've been pointed to method of ...
5
votes
2answers
453 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 ...
5
votes
1answer
301 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 ...
10
votes
3answers
750 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 ...
7
votes
4answers
546 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
3answers
225 views

Testing for stability of a simulated dynamical system

Background and question I often work with simulations of dynamical systems and I usually track a single parameter $x$, such as the number of agents (for agents based models) or the error rate (for ...
-2
votes
1answer
290 views

Multi-objective optimization problem - Euclidean space

I am looking for some clues for an optimization problem. My problem consists on arriving to a image by optimizing multiple layers with the pixel position probability. This is an overview of the ...
3
votes
1answer
377 views

Testing a simple polygon for monotonicity in linear time question

I'm looking for the algorithm of Preparata and Supowit for testing a simple polygon for monotonicity in linear time. I've found it referenced in many textbooks but I can't find the algorithm itself. ...
19
votes
3answers
1k 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 ...
7
votes
6answers
5k 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?
6
votes
1answer
419 views

An efficient 'drizzle' algorithm?

What efficient implementations of a 'drizzle' algorithm are available? The problem is, given a timestream of data in which each element is associated with a pixel in a map, how do you create that map?...
3
votes
1answer
162 views

Global optimal sequence alignment algorithms

As far as global optimal sequence alignment goes, is the Needleman-Wunsch and Hirschberg's algorithm still state of the art? Or have there been any improvements to these algorithms since they were ...
23
votes
1answer
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 ...
7
votes
1answer
196 views

Optimal way to find stationary solutions of the PDE

I am researching heat diffusion in an optical element irradiated by laser. This problem is described by the PDE which I wrote down in this question. I am using an implicit numerical scheme to model ...
17
votes
3answers
318 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 ...
19
votes
4answers
3k 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 ...
23
votes
6answers
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?
42
votes
7answers
4k 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 ...
18
votes
2answers
287 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,...
16
votes
3answers
255 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. ...
7
votes
1answer
996 views

Alternative to Bron-Kerbosch algorithm for enumerating maximal cliques in inverse interval graphs

I often use inverse interval graphs to represent biologically relevant features along a genomic sequence. For example, given a (relatively) small genomic region, the graph would contain a node for ...