Questions tagged [algorithms]

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

Filter by
Sorted by
Tagged with
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
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 ...
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
81 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
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 ...
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 ...
10
votes
3answers
808 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 ...
3
votes
1answer
419 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. ...
6
votes
1answer
496 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?...
17
votes
3answers
348 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 ...
24
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 ...
3
votes
1answer
174 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 ...
7
votes
1answer
221 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 ...
16
votes
3answers
279 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. ...

1
7 8 9 10
11