Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
571
questions
0
votes
1
answer
50
views
algorithm to assign points to winning users
I have a set of users who have won a game
('jim', 12), ('james', 54), ('john', 76), ('dave', 22), ('garry', 34), ('stuart', 16)
I want to award them a share of ...
- 3
3
votes
1
answer
3k
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 ...
- 259
7
votes
2
answers
4k
views
Is there a fast way to compute histograms for high-dimensional large datasets?
Currently the way I compute histograms for data is by generating grid in $N$ dimensions (where $N$ is the dimension of the data) and searching through the $M$ data points in each dimension to see in ...
- 265
6
votes
3
answers
7k
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 ...
- 203
4
votes
1
answer
223
views
Molecular dynamics simulation: fluctuating dipole model implementation
I'm conducting a molecular dynamics simulation for silica. Some time ago I turned to the fluctuating dipole model, and after much effort I'm still having problems implementing it.
In short, all ...
- 41
4
votes
2
answers
221
views
Optimization algorithm selection for 3 variable integer
I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$
it is very expensive to evaluate
$x,y,z \in \mathbb{Z}$
0 < x < 10
0 < y < 30
0 < z < 100
I thought it was convex, not sure ...
- 141
1
vote
0
answers
67
views
Looking for a java library or algorithm for efficiently implementing the second Chebyshev function
Does anyone know of a java library or algorithm for efficiently implementing the second Chebyshev function?
To be clear, I'm refering to this expression:
$$\vartheta(x) = \sum_{p \le x}\log p$$
$$\...
- 111
2
votes
1
answer
1k
views
Convergence of GMRES
From what I understand the GMRES method is (using Arnoldi Iterations/Modified Gram-Schmidt):
The first vector of the Krylov subspace span of A is the normalized vector $\frac{\vec b - A\vec x_0} {|| \...
- 2,694
1
vote
2
answers
560
views
Is there any 1-D test case for incompressible flow codes?
There is quasi 1-D C-D nozzle test case for compressible flow codes, like that "is there any 1-D test case for incompressible flow codes?"
- 489
4
votes
2
answers
247
views
Problem Condition and Algorithm Stability
Consider 2 mathematical problems:
$$
f_1(x) = a - x \\
f_2(x) = e^x -1
$$
The condition number for a function is defined as follows:
$$
k(f) = \left| x \cdot \frac{f'}{f} \right|
$$
Lets analyze ...
0
votes
1
answer
211
views
Neighbor pattern look-up table enumeration on an octree mesh
I am working with an octree mesh where variables are stored in a collocated fashion at octant centers. I want to construct a lookup table for interpolation weights that may occur using only a cell and ...
- 316
7
votes
5
answers
12k
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} & { } & { }...
- 345
3
votes
1
answer
72
views
Library for solving a linear selection problem in a distributed memory machine
I need to solve a very large O(10^10) linear selection problem in a distributed memory machine, is there any library that will solve it for me?
In shared memory ...
- 1,075
11
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 ...
- 211
0
votes
1
answer
108
views
Confusion related to P and NP problems
I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is ...
- 473
1
vote
1
answer
144
views
How to calculate the complexity of a given Algorithm
I have the following algorithm given:
Input: Regular Matrix $A \in \mathbb R^{n,n}$
Output: LU-Decomposition of A = LU
for k = 1, . . . , n do
for j = k, . . . , n do
$r_{kj} = a_{kj} − \sum_{i=1}^...
- 11
1
vote
3
answers
3k
views
Color frequency of a pixel
Is it possible to calculate the color frequency of a pixel?
I mean, I get a pixel that is red but where this red sits on the spectrum in hertz?
Is this even possible to do even in a limited way?
...
- 119
13
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, ...
4
votes
1
answer
2k
views
Implementing the $\theta$-method for solving an IVP
I also posted this question on the Math SE site, but it was suggested I post here also.
I want to implement the $\theta$-method to solve an IVP in MATLAB. The $\theta$-method is:
$y_{j+1} = y_j + h[\...
- 143
8
votes
1
answer
493
views
What is the correct formulation of this "shopping bag" optimization problem, and how can I solve it efficiently?
I'm looking at finding a solution to the following problem, but I'm having trouble formulating it sensibly, and then finding an appropriate algorithm to solve it.
Consider a list of items placed in a ...
- 181
3
votes
0
answers
117
views
Dissipation and symplectic manifolds
I'm working on an API for simulation of port-Hamiltonian systems. As far as I understand it, a Hamiltonian system is symplectic if it is power conserving, and so including resistive elements would ...
2
votes
0
answers
124
views
Algorithm to distribute symbols uniformly in a square grid?
Given a square grid of size $n\times n$ and $m$ symbols (say for example, alphabets A, B, C...), having $N(i)$ number of $i$th symbol; $\sum_{i=1}^{m}N(i) = n\times n$. Is there any computationally ...
- 21
2
votes
2
answers
66
views
Clustering Algorithm for a congruence relation?
Say we are given a congruence relation$~\sim$ in a dataset with $n$ elements. I am looking for an algorithm for optimally sorting the $n$ elements into $m$ clusters according to given congruence ...
- 155
-1
votes
1
answer
65
views
Is it possible to find a formula for a set of number from the result? [closed]
I have these two sets of number, I also have a result. Is it possible to compute
the relation between them so that I can figure out how the result is generated ?
for example I have :
Set A=4 6 12 25 ...
- 1
8
votes
2
answers
322
views
Looking for an algorithm that allocates climbing hold colors to wall sectors
I posted this question earlier on stackoverflow, where it was closed as off-topic. I hope it survives here.
I our climbing gym, the routes need to be re-set from time to time. The following rules ...
- 245
4
votes
4
answers
8k
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 ...
- 178
5
votes
3
answers
235
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 ...
- 151
3
votes
0
answers
80
views
Parallel algorithm to use in place of PORTA?
We currently use PORTA software to find the list of facet-defining inequalities (FDI) for polytopes that we work with. For certain polytopes, PORTA works fine. But because it is a serial algorithm (...
- 31
4
votes
1
answer
2k
views
Multi-objectives fitness function with hard and soft constraints
Background
I am using genetic algorithm to solve the multiple-traveling-salesman problem. It work fine when I have only one constraint (distance) for my fitness function: ie: the lower the total ...
5
votes
1
answer
921
views
Eigenvalue Decomposition of Hermitian Matrix in Scala
I'm working on helping my friend create code to perform the Overlap Dirac Operator and have come across one part that I'm not sure what to do.
I need to compute the Eigenvalues and corresponding ...
- 161
2
votes
2
answers
215
views
Finding two shortest path that are 'distant' in the graph
The problem is as follows:
We are given a graph with each edge length 1 and two pairs of vertices (a,b) and (c,d).
How to find shortest paths between from a to b and from c to d, with assumption that ...
- 121
3
votes
0
answers
114
views
exact area resampling [closed]
I do image processing, and right now I need to resample some images taken from slightly different perspectives so I can match up features. The pixel intensities have scientific significance, so I want ...
- 131
8
votes
1
answer
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 ...
- 287
6
votes
1
answer
838
views
Nonlinear dynamics: algorithm suggest
I've just started a thesis on nonlinear dynamics which entails numerical analysis of the Duffing oscillator (DO). It's basically just a second order ODE, or equivalently a set of ODEs.
Say, after ...
- 315
3
votes
1
answer
100
views
Improve optimization over 'mapping' of indices
I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference ...
- 343
12
votes
2
answers
726
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
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
5
votes
2
answers
1k
views
How to find all complex roots of an equation in a domain
I am facing a problem where I want to find the complex roots of $f(z)=z-sin(z)=0$ numerically.
There are infinitely many roots of the function, but I am only interested in the $N$ closest to the ...
- 155
8
votes
3
answers
4k
views
What is the criteria for switching between Strassen's and Regular matrix multiplication Algorithms
Strassen’s Matrix Multiplication algorithm has theoretical performance of $ O( n^{log_2 7}) $. Regular MM algorithm has performance of $ O( n^{3}) $.
At certain sizes of matrices (lets call it $n*n$),...
- 231
2
votes
2
answers
6k
views
Implementing PageRank using the Power Method
I am trying to implement the PageRank algorithm described in this paper (Fig. 1). Here is the breakdown of the steps:
http://www.louismullie.com/algo.png
where:
...
- 123
3
votes
1
answer
89
views
Randomly choose among N alternatives
I understand how to generate a random sequence of binary variables where 1 occurs with probability p and ...
- 163
6
votes
1
answer
401
views
Ray casting algorithm for multiple disjoint polygons is still valid?
We're dealing with country borders, that is the set of multiple disjoint domains that is made of polygons.
To extract the different point on the map by a given country we've been said to implement ...
- 161
12
votes
1
answer
549
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
5
votes
1
answer
63
views
correct complexity notation
I have written an algorithm where the 2 input arguments are a file and a list of values. I would like to say the algorithm complexity is:
...
- 153
1
vote
1
answer
261
views
Test set non linear solver
what is your preferred test set to test quality of non linear solver?
this could be set of data, model and results obtained with some benchmark solver, or simply a panel of test functions that could ...
- 343
6
votes
4
answers
4k
views
Simulated Annealing proof of convergence
I implemented downhill simplex simulated annealing algorithm. Algorithm is very hard to tune, w.r.t. parameters including cooling schedule, starting temperature...
My first question is about ...
- 343
3
votes
1
answer
396
views
Parallelization of LSE solvers using CUDA
I want to know methods which are fully parallelizable on CUDA architecture.
I have implemented the Jacobi and Conjugate Gradient methods and now Im thinking about the Bi-Conjugate gradient method. I ...
- 155
3
votes
1
answer
176
views
How to add perturbation to a base state in physical grid space?
For study 3D instabilities problem i.e a base state (velocity field and temperature field) and an additional perturbation.
The method must be independent of the type of instabilities considered but ...
- 419
6
votes
1
answer
12k
views
Concave polygon 'hull' finding
I implemented an algorithm to find the alpha shape of a set of points. The alpha shape is a concave hull for a set of points, whose shape depends on a parameter alpha deciding which points make up the ...
- 343
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$...
- 12k