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.

1
vote
0answers
84 views

Low memory algorithm for matrix diagonalisation

I'm trying to find the largest eigenvalues of very large $N \times N$ matrices ($N = 10^{10}$ and larger). The matrices are not sparse but the multiplication operation is fast. For now, I'm using ...
0
votes
1answer
42 views

Algorithm to adjust range / scale so it is “nicley” dividable by n

Hard to come up with a good title. I'm looking for an algorithm to adjust a range. Say I have 5.34 as min and 23.96 as max value. This gives it a range/difference of 18.62. I now want to divide this ...
1
vote
1answer
108 views

Bulirsch-Stoer algorithm to solve simple chemistry. Spanning long time intervals after stationarity

Hi all and thank you in advance. I am working on a time-dependent transport-chemistry model to study the composition of planetary atmospheres. The equations are the following $$\frac{\partial n(z,t)}...
1
vote
0answers
51 views

Algorithm design to filter on 5,000 stocks each of which has 4 months worth of data points

I want to filter on 5000 stocks, each of which has 4 month or more worth of data (>= 500 data points each). my filtering criteria will be based on 8 calculated values from the data points. for example,...
3
votes
2answers
125 views

How does Mathematica compute real and complex solutions to single, non-polynomial equations?

This question on StackOverflow has led me to ask myself what would be involved in solving an equation like this one using tools available to the Python programmer. $$ \frac{0.125567841}{d^{2.25}} = \...
5
votes
1answer
125 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
3
votes
1answer
191 views

How to compute the Frobenius norm of matrices whose entries are either too large or too small?

While implementing in Matlab the Frobenius norm of a matrix $$\| A\|_{\text F} := \sqrt{ \sum_{i=1}^m \sum_{j=1}^n a_{ij}^2 },$$ a problem arises when numbers are too big or too small: If a number ...
1
vote
0answers
95 views

Linear regression with inequality constraint in Java

I haven't been doing math in years and I'm facing the following problem. I'm trying to implement in Java a linear regression under a set of inequality constraints. Sorry in advance for all the ...
0
votes
1answer
935 views

When doing a linear regression, what is the fastest/slowest regularizer?

Let's say I am doing a linear regression on a large dataset and I only care about computational speed, which of the following regularizers should I use and which should I absolutely not use? $L_0$ -...
1
vote
1answer
181 views

Methods for solving $Ax=b$, small and sparse A

I'm trying to solve/implement a system of linear equations of the following form/structure: $$ Ax=b$$ $$A = \begin{bmatrix} * & * & 0 & * & -1 & 0 & 0 & 0 \cr * & * &...
1
vote
1answer
256 views

Kronecker product among multiple arrays

I was wondering whether there is a smart and efficient way in Matlab to compute the kronecker product of several 1D arrays. What I mean is something like this ...
1
vote
0answers
82 views

How to choose seed in flood/fill algorithm

I was able to draw to the outer airtight boundary of hole. Now I would like to implement interior flood/fill algorithm. To get an internal seed, only one method comes to my mind which is testing ...
0
votes
1answer
156 views

Hypergraph matching -> adjacency matrix?

I need to do a matching on a hypergraph. I read that in the case of a hypergraph there is no adjacency matrix. How do I represent edges then?
3
votes
1answer
72 views

Description of algorithm for small scale linear least squares with box constraints

I have small scale dense least squares problem with box constraints $$\mbox{argmin}||Ax - b||^2 \quad $$ $$\mbox{subject to} \quad l_i \leq x_i \leq u_i,$$ Number of variables is about 10-50, ...
1
vote
1answer
123 views

Algorithms for the one-to-two assignment problem

I can't seem to find a good algorithm for the one-to-exactly-two assignment problem. Good algorithms are known for the classical assignment problem, where N tasks need to be assigned to to M agents in ...
12
votes
2answers
618 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
vote
0answers
74 views

Computing the change of function at two close points without cancellation

I want to compute the difference $\Delta f(x_1,x_2) = f(x_1)-f(x_2)$ of a smooth function $f(x)$ at two points $x_1$ and $x_2$ which are close to each other. The magnitude of the expected result, $|\...
0
votes
1answer
133 views

Fast chain rule algorithm [closed]

Assume I have two functions $f$ and $g$, with derivatives of $g$ at point $x$ and derivatives of $f$ at point $g(x)$ available. What is the fastest way of computing derivatives of $f \circ g (x)$ ?
1
vote
1answer
37 views

Filter coefficients for convolutional inpainting

I'm working on a project that requires unknown image elements to be filled in, and am using a simple inpainting algorithm, which I would like to understand better. It works by repeatedly convolving a ...
6
votes
1answer
83 views

Stable computation of ratio of sums of large numbers

I have two sets of large positive numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$. By 'large' I mean of the order of $10^{10}$. I want to calculate the ratio $$R = \frac{a_1 - a_2 + \cdots +(-1)^{n+1}...
1
vote
1answer
328 views

Sieve of Eratosthenes with minimized memory usage [closed]

Originally sieve of Eratosthenes requires a lot of memory. This algorithm is my attempt to limit the memory usage. In fact it requires ln(N) memory (for each found prime number we keep last crossed ...
0
votes
1answer
50 views

Maximize sum(AI) for matrix A and any permutation of identity matrix I

I have a random binary matrix $A$ $$ A=\left[\begin{array}{c c c c c}0&0&0&0&1\\0&1&0&1&0\\1&1&1&1&0\\0&1&1&0&0\\1&0&1&1&...
0
votes
1answer
152 views

Find hidden sequence $a_n = a_{n-1} + T $ , with period $T$, given some “random” numbers

I have this data plotted on a graph in which all points have the same value on the y-axis, e.g a constant integer "c", while the x-axis is the time in seconds. So, for a c = 25 on the y-axis, there ...
0
votes
2answers
60 views

Physical meaning behind the choice of the proposal distribution in Markov Chain Monte Carlo (MCMC) methods

Let us consider the conventions on names used in the theoretical derivation of Metropolis-Hastings Monte Carlo as outlined here, for the sake of common nomenclature. What we are building is a step-...
2
votes
2answers
83 views

How can I find positive integers $a$ and $p$ satisfying $a^{p-1}=1($mod $p^2)$?

How can I find positive integers $a$ and $p$ satisfying $a^{p-1}=1$ ($\mathrm{mod}\ p^2$)? Let's say $1\lt a \lt 100, p \lt 10^8$.
1
vote
0answers
24 views

How group similar data in a single classes and reduce the error

I have vehicles gps information in my real time traffic application. Averaging that information I know the speed of every road at any time. The problem is that is too much data to send back to the ...
0
votes
1answer
52 views

Efficient search strategy in a monotonic boolean function wherein the probability of solution location is known apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
4
votes
0answers
91 views

How can I evaluate the accuracy of my n-body simulation?

I am making an n-body simulation in python. There are many different methods to numerically solve the system of differential equations governing the gravitational interactions between the $n$ ...
0
votes
1answer
318 views

Solving an equation in space and time using the Crank-Nicolson approach

Assume I have the following equation (light propagating in $z$-direction through the matter): $$id_zu+d^2_ru=0$$ with $u(z, r)$ being a complex wave. The time scale in this equation is $$t\equiv t_\...
0
votes
1answer
138 views

Hankel transform from paper works only for certain functions

I implemented an algorithm for solving the Hankel transformation based on a paper. My problem is: It works very good for the functions suggested in the paper (as test functions), it works pretty ok ...
2
votes
1answer
118 views

How does Mathematica compute 'Reduce'?

I submit a Reduce command and get results like this: ...
1
vote
1answer
97 views

Efficiently determine whether a curve intersects a given rectangle?

Suppose we have a straight line in Cartesian space such that $$ x_k = x_0 + k \delta x, \quad \quad y_k = y_0 + k \delta y, \quad \quad z_k = z_0 + k \delta z $$ where $k$ can take any real value. If ...
1
vote
1answer
78 views

Why rational numbers in the Lenstra–Lenstra–Lovász algorithm?

The Lenstra–Lenstra–Lovász (LLL) algorithm is a famous one for lattice reduction. But concerning its application, I am always baffled by one point. The algorithm applies equally well to irrational ...
0
votes
1answer
297 views

Algorithm to find all quadratic residues modulo $n$

An element $a \in \mathbb{Z}_n$ is a quadratic residue in $\mathbb{Z}_n$ if it's congruent to some perfect square modulo $n$. Is there an efficient algorithm to find all quadratic residues in $\...
1
vote
0answers
24 views

Is there an algorithm on python for analyzing swarming behavior or a modeling algorithm to predict swarming behavior? [closed]

Is there an algorithm on python to analyze swarming behavior or model swarming behavior for predictions?
0
votes
1answer
3k views

Backtracking-Armijo Line Search Algorithm

EDIT based on comments below: I add the mathematical formulation of my problem below. I am trying to solve an equation of the form $$ \partial_t f(x,y,t)= (\partial^2_x +\partial^2_y) f(x,y,t) \equiv ...
-1
votes
1answer
4k 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 ...
1
vote
0answers
47 views

The right algorithm to predict from selected data samples [closed]

I'm trying to come up with the right algorithm for a system in which the user enters a few symptoms and the system has to predict or determine the likelihood that a few selected symptoms are ...
1
vote
0answers
53 views

Comparing the solutions to a multi-objective optimization problem

Suppose I have a multi-objective optimization problem, and I wish to find solutions using two different methods/algorithms. The result of each algorithms is a Pareto front. Comparing two different ...
1
vote
0answers
72 views

How does this Constrained Minimization algorithm work?

I don't fully understand the subsection 3.2 Constrained minimization of this paper. In particular, I don't understand the first step "Register active set" and the definition of projection $P(x)$. ...
2
votes
0answers
224 views

sum of n numbers with the power k

I am searching for a good algorithm to solve problem 487 on project-euler. I dont want code or something like that, I only want the name of the algorithm thats best suited. Till now I think of either ...
0
votes
1answer
111 views

Error Reduction algorithm for single measurement intensity [closed]

I'm trying to solve the phase problem from single intensity measurement. I implemented error reduction algorithm in Matlab for ...
3
votes
0answers
93 views

Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
1
vote
2answers
548 views

LU decomposition of large dense matrices

I wanted to generate LU decomposition of large size dense matrices ($N>10^7$), the LU decomposition I'm currently using is based on Adaptive Cross Approximation and is taking very long time to ...
0
votes
1answer
48 views

Passing in a vector from this particular matrix class floating around online [closed]

I am using this matrix class here to assist me in converting this Least Squares algorithm that prices American options that is written in Matlab in C++. My question is pretty simple. I want to pass in ...
0
votes
1answer
452 views

Can a Depth first traversal of a graph visit node more than once? [closed]

Is there a way in which Depth First Traversal will put a node into the stack more than once using the general algorithm as shown here. Also, is it compulsory for all nodes to be entered into the ...
0
votes
3answers
282 views

Full segmentation of a linear space using a clustering algorithm

Once again, I am not entirely sure how to describe what I am looking for, hence I have a hard time finding answers using Google or any other literal search method. Let's say I have a time series: $$(...
4
votes
0answers
78 views

Computing Algebraic Riccati inequality

In my Robust model control, I have got a couple of quadratic Riccati inequalities which need to be solved numerically on MATLAB. My question, Is there function on MATLAB can solve quadratic Riccati ...
1
vote
1answer
134 views

Connections between Map Reduce operations and Linear Algebra [closed]

I am interested with Map and Reduce operations in computer science. I would like to do analogies with Mathematics and especially ...
1
vote
0answers
83 views

QR via Householder: less computationally complex variants?

I'm a probabilist and need to do a few computations for a rather big linear least squares problem, so I'm trying to optimize the computation as far as is feasible to me. In computing the QR ...