The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
94 views

Fitting algebraic expression to a number [algorithm]

I know that it may turn out useless, but this is precisely the reason why I'm asking. Does any one know of an existing piece of code that would find me the best approximation to a given irrational ...
3
votes
1answer
144 views

Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...
2
votes
1answer
328 views

At what point does Miller-Rabin become faster than trial division?

I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$. My question is: how ...
0
votes
0answers
103 views

max*min/(max+min) vs max*min/(max-min)

While working on a genetic algorithm, I needed to devise a fitness function for each chromosome. Each chromosome has 2 attributes: maximum accuracy and minimum accuracy. The fitness should increase ...
0
votes
0answers
77 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
0
votes
2answers
61 views

Maximize 2-tuple efficiently

Hello I am lookin for an algorithm that efficiently finds all Tuples ${(x,y)$$\varepsilon U|\forall (u,w) \epsilon U \rightarrow (x>=u \vee y>=w)$. I could of course check all tuples against ...
3
votes
0answers
194 views

(Co)limit computations for diagrams of Vector Spaces

Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...
2
votes
1answer
166 views

Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways: 1- Mark ...
1
vote
0answers
120 views

regular hyper graph construction

Is there any algorithm to generate 3-uniform k-regular hypergraph with n vertices?? Any help is appreciated. Thanks.
1
vote
0answers
131 views

Optimize a convex hull on a 2D histogram so the selected points match a target shape

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...
2
votes
1answer
369 views

Removing cycles from an undirected connected bipartite graph in a special manner

Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We ...
9
votes
2answers
596 views

When polynomial f(x^2) can be factored as g(x)·g(-x) ?

In relation to my question Expression for the sum of square roots of zeros of a polynomial How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where ...
2
votes
1answer
166 views

algorithmic almost equitable partitioning

Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...
0
votes
0answers
120 views

Find polynomial in finite field

We have $A$, $B \in GF(q^k)$ We want to find polynomial $h \in GF(q)[x]$ where $h(A) = B$ What is the lowest degree of $h$? How to find $h$ with the lowest degree and what is complexity of this ...
2
votes
0answers
45 views

Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case

I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...
2
votes
5answers
913 views

Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details. Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, ...
1
vote
1answer
290 views

Find root in finite field

What efficient algorithms exist for the solving $x^N = a$ in GF(q)? What are their complexities?
1
vote
1answer
271 views

calculate function from its divizor

There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$. There is algebraic function f on C. We have div(f). How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + ...
2
votes
0answers
189 views

Choosing a base where a given digit of a given number appears the most times

Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)
0
votes
0answers
154 views

Condition and algorithm for Decomposition of formal power series

$$F(x)= \Sigma_0^{\infty} a_i x^i$$ is formal power series, $a_i\in N\bigcup 0$,N is the set of natural number,under what condition may it be decomposed into a system of equations terms of which are ...
0
votes
2answers
236 views

Enlcosing a set of ellipses within one ellipse

Hello, Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?
1
vote
0answers
83 views

Toroidality testing

Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer-Myrvold algorithm (which has a MATLAB implementation) and would like to know if there is something ...
4
votes
1answer
233 views

Generating non-isomorphic graphs by adding edges to a given graph

Hello! This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here! I am given a fairly large graph $G$ and ...
6
votes
1answer
366 views

Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
0
votes
0answers
94 views

Examples of applications that use the Schnorr digital signature?

Hi there. It may not be the best place to ask this question, but here goes: I have made a study on digital signatures, especially on the Schnorr digital signature, and I was just wandering if there ...
3
votes
1answer
103 views

Search for common substructures in list of graphs

I have had the following problem on several occasions and I was wondering whether there is a general technique to solve this problem. Given a list of graphs with property $P$. Is there a general ...
0
votes
1answer
154 views

An Algorithm to Determine a probable profit

I 'm searching for an algorithm (and except the naive brute force solution had no luck) that efficiently ($O(n^2)$preferably) does the following: Supposing I’m playing a game and in this game I’ll ...
2
votes
1answer
271 views

Finding a subspace disjoint from a union of subspaces

Let $k$ be a finite field (I care about $\mathbb F_p$, especially $\mathbb F_2$) and let $V_1,...,V_N\subset k^n$ be subspaces. I want to find a subspace $S\subset k^n$ such that $S\cap V_i=0$ for ...
8
votes
1answer
358 views

Constructive proof of “Projective implies proper”

For every ring $A$, the structural morphism of schemes $\pi_A : {\bf P}^n_{A} \to {\rm Spec}{A}$ is a closed map. The usual proof of this fact is not constructive : given equations of a closed subset ...
16
votes
3answers
842 views

Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute $f(x)$. The input consists of the digits of $x$ and the output of a rational number approximating $f(x)$. A function $f$ is called ...
6
votes
1answer
243 views

How do you compute the primes of bad reduction?

Suppose that I am given a subscheme $Y$ of $\mathbf{P}^n_{\mathbf{Z}}$, flat over $\operatorname{Spec}\mathbf{Z}$ and with smooth generic fiber $Y_{\mathbf{Q}}$, defined by the vanishing of some ...
4
votes
1answer
391 views

Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...
0
votes
2answers
262 views

Creating composite rank [closed]

Problem: Suppose that $K$ different students are ranked based on $N$ different parameters (such as Physics marks, English marks, Biology marks, IQ etc). The rank under each parameter can be repetitive ...
7
votes
1answer
314 views

Experimental mathematics: how are floating point equations discovered/converted to exact equations?

the 2005 AMS article/survey on experimental mathematics[1] by Bailey/Borwein mentions many remarkable successes in the field including new formulas for $\pi$ that were discovered via the PSLQ ...
2
votes
1answer
198 views

An optimization problem, non complete bipartite graph and hungarian algorithm

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 the rows in reference dataset with the ...
4
votes
2answers
151 views

Computing Slim Extensions representing Ext

Hey Everyone Let $A$ be an algebra over a field (group rings $k[G]$ for group cohomology, the Steenrod Algebra). We want to compute, say, $Ext_A(k,k)$, so let $F_*\to k$ be an $A$-free resolution. ...
0
votes
3answers
628 views

Largest subarray with average $\geq$ k

I try to solve this problem. The algorithm I developped has a complexity of $O(n^2)$. When dealing with large data the program is brought to its knees. Do you have any idea that might be faster than a ...
0
votes
2answers
179 views

Maximizing number of factors contributing in the sum of sorted array bounded by a value

I have a sorted array of integers of size n. These values are not unique. What I need to do is : Given a B, I need to find an i<A[n] such that the sum of ...
6
votes
1answer
232 views

Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?

I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in ...
3
votes
1answer
110 views

Median-of-k elements

Hello, Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$. Then out ...
2
votes
1answer
225 views

Complexity of establishing finite groups (non)-isomorphism ?

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...
8
votes
3answers
1k views

Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ? (Main case - complex numbers, comments on other cases are also welcome. "Given" ...
2
votes
2answers
250 views

Lattice reduction on an orthonormal lattice?

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you ...
0
votes
1answer
93 views

Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

I have a set of $(l_1, ..., l_N) \in L$ smaller sets, each with $(r_1, ..., r_M) \in R$ integer elements. I would like create an ordered array of $(q_1, ..., q_N) \in Q$ sets s.t.: (1) Each $q_i \in ...
9
votes
1answer
292 views

Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)

Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$. Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix ...
1
vote
1answer
255 views

Computing the ratio of two large integers modulo m

$P(n)$ and $D(n)$ are two large integers. Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer. I want to compute $R(n)\bmod m$. $P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and ...
0
votes
1answer
510 views

Finding the lowest cost set of disjoint paths using all nodes in a directed graph?

I have a directed graph with edges connecting nodes representing costs. I wish to find the set of paths which -go from node 'start' to node 'end' -are node-disjoint (except for the start and end ...
1
vote
5answers
1k views

The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure. Thanks
1
vote
0answers
123 views

Efficient algorithm for computing the integral closure of a computable domain

what is known? even talking about efficiency relatively to the complexity of the computation of the domain itself?
6
votes
2answers
449 views

Algorithm for reducing words in a Coxeter group

Let $W$ be a Coxeter group with set of simple reflections $S$. Suppose that I have chosen a preferred reduced decomposition for every element of $W$. Given an arbitrary word in the alphabet $S$, is ...