Questions tagged [mathematical-programming]
Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.
2
votes
0answers
31 views
Maximizing the product of a set of dot products
So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following:
$\prod_{x \in X} b \cdot x$
where the components of $b$ sum to $1$
If it matters the components of ...
2
votes
2answers
944 views
How does a computer interpret real numbers?
I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers.
But I want to know how does ...
3
votes
1answer
83 views
Can this equation be solved in polynomial time?
I came across a more general form of this question.
Can we find the value of variables in polynomial time ?
Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
6
votes
2answers
142 views
Can this system of polynomial equations be solved in polynomial time?
I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
2
votes
1answer
23 views
Interpolate on a cylic x axes
Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y ...
1
vote
0answers
20 views
How can I code an algorithm (concerning networks) [closed]
my question is basic but I want to know how to code algorithms containing maths like this https://web.stanford.edu/~skatti/pubs/sigcomm15-spotfi.pdf , TY for your help !
0
votes
0answers
21 views
Optimize an underdetermined system with quartic constraints
I encountered an optimization problem which does not belong to any well-known category of optimization.
The system has $M$ (typically $M=120$) real variables and $N$ (typically $N=100$) constraints (...
1
vote
0answers
51 views
Sum of long geometric progression [closed]
Finding sum of a geometric progression is simple when we just need to report the sum,
but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.
I have a ...
0
votes
0answers
28 views
How to generate evenly distributed random numbers from the tics of a Geiger Counter?
How can I generate random numbers from the tics of a Geiger Counter?
Say I have a file with the timestamps for every event.
0
325
456
920
....
The time spans ...
1
vote
0answers
28 views
How much of the x86 instruction set does blender use? [closed]
I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
0
votes
0answers
24 views
Algorithm for placing objects inside a square from outside to inside
I have a map that is 300x300 units. I have to place squares of 20x20 units inside that map from outside to inside. There are 3 different types of square, the space available inside the map needs to be ...
0
votes
1answer
48 views
Counting the number of multiples of number A that perfectly divides the number B
What is the best way of counting the number of multiples of number A that perfectly divides the number B.
This is the sub problem for one of the questions I am solving on codechef.
This is the best I ...
1
vote
1answer
65 views
Mathematically calculating time complexity
This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.
Also I ...
4
votes
0answers
98 views
Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$
We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$.
The obvious naive way ...
0
votes
1answer
55 views
0
votes
0answers
54 views
What is the time complexity of MATLAB's ode solvers?
Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in ...
2
votes
1answer
40 views
Implementing Gauss–Legendre algorithm using arbitrary-length rationals
I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate. SuperPI computes pi using the Gauss-Legendre algorithm.
The Gauss–Legendre algorithm is quite simple, ...
1
vote
1answer
22 views
What is the equation for a spiral path in 3D? [closed]
I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.
Would ...
0
votes
0answers
25 views
Classify manifolds with neural networks
Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?
1
vote
1answer
45 views
Balance groups based on average, element constraints and size
It's a complex situation, where I want to balance groups of numbers based on the average of these numbers, while keeping the group size unchanged and not breaking elements constraints.
Let me explain ...
2
votes
1answer
135 views
Implications of Integral linear program
Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$
Let $(P^*)$ be ...
1
vote
1answer
169 views
Efficient streaming sort
Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id &...
2
votes
1answer
53 views
Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$
Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I ...
1
vote
1answer
17 views
PCA with Bishop's book
I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u_1$ or $u^T_1$?
Your help is ...
0
votes
1answer
58 views
Compute e^x given starting approximation
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits). The best way I know is to use Taylor polynomials. However, the Taylor polynomial algorithm seems ...
1
vote
1answer
22 views
Sum of distances between points on one-dimensional axis
We have given integer array of $n$ points, let it be $A$, showing where it is on the x-axis. For this problem we are working only with the x-axis and the y-axis is not important at all. Now for given ...
3
votes
3answers
163 views
Is it possible to make a language that can build upon itself perfectly?
First of all, note that I'll have to explain my thoughts in a layman's terms.
There are so many high-level programming languages out there that compete with each other. This means we have to build ...
0
votes
2answers
566 views
Is global non-convex optimization NP-complete?
Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision ...
0
votes
1answer
36 views
How do you implement a language with greater capabilities using subordinate languages?
I've heard that C++ and Python where implemented using C. How can someone make an object oriented language out of something that doesn't support objects?
I've read in the book "Math You Can`t Use - ...
1
vote
1answer
119 views
Algorithm for weighted elliptic curve fit
Background:
I was trying to detect a face solely on the bases of features and the confidence of the features found.
I am using a method to identify the features along with the response (confidence). ...
0
votes
1answer
119 views
Is there a poly-time algorithm for expanding out polynomials
so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of
$$
z = (x+y)(x-y) \implies x^2+xy-xy+y^2
$$
...
1
vote
1answer
80 views
Is it possible to evaluate $n!$ in $O(1)$?
I'm working on a formula that'll evaluate the partial sum of the harmonic series from $t_1$ to $t_n$. The problem is that I'm almost certain the final formula will include factorials. But if the ...
1
vote
2answers
115 views
Algorithm for packing various shapes inside of a rectangle
Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as ...
1
vote
0answers
220 views
Understanding Sliding Window Algorithm
I am trying to implement sliding window algorithm for rainfall forecasting. The algorithm is follows:
This algorithm is from An enhancement of sliding window algorithm for
rainfall forecasting in ...
4
votes
2answers
247 views
Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?
The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are:
Does the $x$ in the ...
0
votes
0answers
51 views
Math behind path tracing
I seem to remember seeing somewhere (many years ago) a writeup of the math behind calculating the outline of Metafont glyphs. The basic idea is you have a "pen" that is a circle or oval, that you ...
1
vote
1answer
95 views
What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?
I'm talking about functions such as Python's math.frexp() :
math.frexp(x)
Return the mantissa and exponent of x as the pair (m, e). m is a float
and e is an integer such that x == m * 2**e ...
0
votes
0answers
325 views
Derivatives involved in Bilinear interpolation
If we choose a unit square in which the four points where the function $f$ is known are as shown in the diagram the interpolation formula for $f$ is:
\begin{equation}
\begin{split}
f(x+u, y+v)\approx (...
1
vote
1answer
55 views
Algorithm which finds the maxmal solution that satisfies the following constraints
I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form:
$k_1 * a_1 + b_1 = x$
$k_2 * a_2 + b_2 = x$
$\dots$
$k_n * a_n + b_n = x$
...
1
vote
0answers
43 views
How to model the constraint of a circle placement problem mathematically?
I have a circle with radius $R$ and $N$ points on a 2D plane with known locations $(x_i,y_i), i=1,2,..N$. I want to place the circle such that it maximizes the number of covered points.
Let $d_i=(x_i-...
0
votes
1answer
57 views
How can I calculate the new quotient if I came to know divisor is increased by one?
If I have two number consider a and b and let their division quotient is c.
I know the value of c but I don't know either value of divided(a) or divisor(b). If I came to know the value of divisor is ...
2
votes
1answer
132 views
How to find the most unique vectors in a set?
A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the ...
2
votes
0answers
117 views
Can cognitive architectures (CLARION, SOAR, ACT-R) be used for creative mathematical reasoning?
Can cognitive architectures (CLARION, SOAR, ACT-R, others) be used for creative mathematical reasoning? As far as I understand, then it is the best to encode formal mathematical knowledge in the ...
1
vote
0answers
58 views
Column Generation - Worst dual bound when adding various columns per iteration
I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative ...
4
votes
1answer
376 views
How did the Logic Theorist proved the Pons Asinorum
I was reading about the Logic Theorist solving many of Whitehead and Russell's Principia's theorems. I cannot however find any technical explanation on how the program proved those theorems and ...
1
vote
1answer
510 views
Why does radix sort work?
I understand how radix sort works and how to implement it, but I don't understand why it works.
Are there any underlying mathematical or logical principles that it relies on?
1
vote
0answers
45 views
Program that solves mechanics diagram problems
There is a program, BEATRIX, that can understand textbook physics problems specified by a combination of English text and a diagram. The result of the understanding process is a unified internal model ...
5
votes
1answer
791 views
n! mod p Fast Factorial
I need to find N! (mod 232-5) such that 0 ≤ N ≤ 264 for i cases, 0 ≤ i ≤ 1000 in 1 sec.
Credits: https://dmoj.ca/problem/factorial2
I am aware that I only have to handle 0 ≤ N ≤ 2 ≤ 232-6 because ...
1
vote
1answer
273 views
Stroke Width Transform: Gradient Direction Computation
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .
Having a simple image with random texts, that underwent gray ...
4
votes
2answers
195 views
Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?
I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing ...
