Computational mathematics involves mathematical research in areas of science where computing plays a central and essential role, emphasizing algorithms, numerical methods, and symbolic methods.
1
vote
1answer
135 views
Exponential Probability Monte Carlo simulation
I need to write a Matlab program to estimate the quantity $\theta = \mathrm{Pr}(X < 1)$, where $X$ is an exponential random variable with mean $1$. I am doing this for multiple monte carlo ...
1
vote
0answers
91 views
Power sums, fast algorithm
I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm ...
2
votes
1answer
47 views
Is regularity is preserved under reversal?
When talking about languages and regular languages.
Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar.
Therefore, the ...
1
vote
2answers
54 views
Solve right linear set equations
Trying to solve this set of equations. I'm feeling like I'm making it so complicated.
Of course + is union. Am I on the right track?
A = 0B + 1D
B = 0C + 1A
C = 0A + 1B + λ
D = OD + 1C + λ
A ...
1
vote
1answer
43 views
Show Two f.s.a. machines accept different input
I'm trying to solve it for two hours already. I know it somehow related to the pumping lemma
Let $M_1 = \langle Q_1,S,f_1,s_1,F_1\rangle$ and $M_2 = \langle Q_2,S,f_2,s_2,F_2\rangle$ be two machines, ...
1
vote
1answer
233 views
Show two finite state machines are equivalent
Suppose $M_1 = \langle Q_1,S,R,f_1,g_1\rangle$ and $M_2 = \langle Q_2,S,R,f_2,g_2\rangle$ are two strongly connected machines.
I need to show that $M_1 \equiv M_2$ iff there exist a state $p \in Q_1$ ...
1
vote
1answer
140 views
Computational Complexity of Modular Exponentiation
The following was posted from a lecture:
"($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method.
$Z_1 = a \bmod N$
$Z_2 = (aZ_1) \bmod N$
$Z_3 = (aZ_2) ...
2
votes
1answer
176 views
radial basis function and neural networks
actually i need a simple explanation consider it for dummies about what is Radial basis function are?and what is the relation between radial basis function and neural networks ?and is there's any ...
2
votes
2answers
96 views
Approximating $\pi$ in Binary
I am interested in creating a Java program that generates digits of $\pi$ (in Binary though). To be clear, the number I'm looking for begins: $11.00100100 \dots$
I am unsure of the most efficient way ...
2
votes
0answers
126 views
Logistic regression algorithm in Casio and Texas Instruments calculators
When using logistic regression on a Casio or Texas Instruments calculator, the output is of the form
$$f(x) = \frac{c}{1+ae^{-bx}} $$
The problem I have (when teaching in a class where both types of ...
0
votes
0answers
110 views
A (contour?) integration (even if by using Mathematica!)
I need to be able to calculate integrals of this type where the sum over $R$ is the sum over representations of a Lie group $G$ on whom $dU$ is the Haar measure and $\chi _ R ()$ is the character of ...
1
vote
1answer
143 views
Is all mathematics computable?
No matter how good a computer is, it will never compute the whole sequence of PI, but we can approximate it to arbitrary degeree. We can also implement programs that can do calculus and linear ...
0
votes
1answer
67 views
Finding if two machines can be equivalent
I have this problem:
Consider the following machines M1 and M2.
M1 has initial state A and the initial state of M2 is unspecified.
Can the machines be made equivalent by the correct choice of ...
1
vote
0answers
88 views
Confusion related to state equivalence of finite state machines
I have this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input ...
0
votes
1answer
71 views
Fast methods to check linearity of differentials? Generalizing linearity?
The L1 Mat-1.1010 -course here has taught me the linearity conditions $f(a x)=a f(x)$ and $f(a+b)=f(a)+f(b)$. I want to generalize it, some quite irrelevant slow investigation here.
It requires time ...
4
votes
0answers
144 views
“Green Globs” question
When I was in high school geometry, we had a fun little game on the computer called Green Globs (the website for the software is http://www.greenglobs.net/index.html). A number of targets (globs) are ...
1
vote
1answer
66 views
Sieve higher powers with logarithmic optimization
I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval:
$\{318, 921, 1526, ...
0
votes
0answers
48 views
Plot randomly oriented gaussian kernel
I would like to plot with scipy randomly oriented gaussian kernels. For a gaussian kernel along x and y axis (with an angle 0 w.r.t. coordinate system), I simply plot function
...
11
votes
1answer
361 views
Quadratic sieve algorithm
I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
3
votes
4answers
161 views
Prime factorization, Composite integers.
Describe how to find a prime factor of 1742399 using at most 441 integer divisions and one square root.
So far I have only square rooted 1742399 to get 1319.9996. I have also tried to find a prime ...
1
vote
1answer
142 views
Given two sets of vectors, how do I find a change of basis that will convert one set to another?
Given two sets of dimension $n$ vectors
$\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$,
where $m > n$, is there a computational method (in particular, using ...
2
votes
2answers
477 views
How to handle big powers on big numbers e.g. $n^{915937897123891}$
I'm struggling with the way to calculate an expression like $n^{915937897123891}$ where $n$ could be really any number between 1 and the power itself.
I'm trying to program (C#) this and therefor ...
2
votes
1answer
224 views
How to compute efficiently the norm of a cyclotomic integer
Let $l$ be an odd prime number and $\zeta$ be a primitive $l$-th root of unity in $\mathbb{C}$.
Let $K = \mathbb{Q}(\zeta)$.
Let $A$ be the ring of algebraic integers in $K$.
Let $\alpha \in A$.
How ...
2
votes
1answer
146 views
Using sympy im Python to substitute values into a 10x10 matrix
'm using the symbolic package sympy to store a 10X10 antisymmetric matrix in terms of 10 variables. and then at every iteration step, i substitute numerical values into the entries of the matrix. ...
0
votes
0answers
28 views
Is a satisfiable FOL-sentence a prime event structure always satisfiable in a regular trace event structure?
Suppose first-order logic sentence is satisfiable in the class of prime event structure. Is it also satisfiable in some regular trace event structure? (for all notions I'm referring to Madhusudan's ...
4
votes
0answers
478 views
Obtain a contradiction
Motivation :
The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
4
votes
1answer
77 views
Hilbert curve scheduling not theoretically well defined?
In high-dimensional task scheduling, it is common to use a Hilbert-curve ordering. Given a set of points $\{p_i\}_{i=1}^N \subset \mathbb{R}^d$ the goal is to linearly order them such that points ...
0
votes
2answers
99 views
Help understanding a $3n+1$ problem programming project
I was going through this website where I found 3n + 1 problem.
I was not able to understand what the output should be.
I ...
0
votes
2answers
113 views
Is there a Mathematical Optimization API? [closed]
I mean something like:
I have to solve a Knapsack problem in my application
I describe an XML with all variables, objectives and more
I Upload this XML to a remote server (via a restful API)
I get ...
2
votes
1answer
181 views
Asymptotic expansion of a special integral
I need an asymptotic expansion of J(n)
$J(n)=\frac {2} {\pi} \int_{0}^{\pi/n} \prod_{k=1}^n \frac {\sin kx} {\sin x} dx$, $n=2,3,4,\dots$
Can anybody help to find the asymptotic analytically or at ...
0
votes
0answers
26 views
generating random density operators
A quantum (mixed or pure) state is a Hermitian, positive semi-definite operator with unit trace. I need to construct states by using available pseudo-random number generators (I personally use ...
1
vote
2answers
128 views
Computational efficiency of Machin-like formulae
From what I have read, it appears that the most efficient methods of calculating $ \pi $ are Machin-like formulae. And it is known that certain formulas are more efficient than others.
Are there any ...
1
vote
1answer
63 views
Minimizing the norm related with iteration method
I am working on a iteration method to compute the generalized inverse of a matrix $A$ of rank $r$
Iteration method is
$X_{k+1} = X_{k} + \beta X_{k} (I - A X_{k}) $
where notations are as follows
...
0
votes
0answers
33 views
the leading term of a module
I'm reading CLO and I have a question about the following Prop:
Let I be an ideal in a polynomial ring $k[x_1,\ldots,x_n]$. Then $k[x_1,\ldots,x_n]/I$ is isomorphic as a $k$-vector space to $S = ...
4
votes
1answer
78 views
Distinction between error estimator and error indicator
When solving differential equations numerically one can incur discretization error and one can construct a posteriori error estimates to approximate the true error. There is a distinction often made ...
0
votes
0answers
94 views
Collaborative modular exponentiation
EDIT: Rephrased.
I have, stored somewhere, the values $a$ , $Q$, $N_1$ (plus its factor) and $a^{2Q} \mod N_1$.
I also know $b$, $R$ and $N_2$ (but not its factors).
I want to know whether there is ...
4
votes
1answer
60 views
Need little hint to prove a theorem from a paper
I have an iterative method \begin{eqnarray}
X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots
\end{eqnarray}
with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
0
votes
0answers
86 views
How a direct method can be compared with an iterative method?
How a direct method can be compared with an iterative method?
I have an iterative method to compute Moore- penrose generalized inverse.
There are some direct methods available to compute Moore-Penrose ...
1
vote
0answers
83 views
Calculation of stopping condition for Conjugate Gradient
I am a person with programming background and need some math help.
I am looking at the source code for an implementation of the Conjugate Gradient iterative solver ...
3
votes
2answers
83 views
Comparison of two very large necklaces
I came across one problem and I would like to find an answer.
It is well-known how to calculate the number of fixed necklaces of length $n$ composed of $a$ types of beads $N(n,a)$.
...
2
votes
2answers
120 views
Value of double product
What is
$$
\prod_{i=1}^n\prod_{j=1}^{n-i}i^2+j^2
$$
?
It feels like there should be some way to simplify this or calculate it more efficiently than iterating over each of the $\sim n^2/2$ points.
...
0
votes
1answer
81 views
more matrix inversion
Related to a previous question: Suppose I want to invert a (sparse) matrix written in block form as
\begin{array}{cccc}
A_{11} & A_{12} & \ldots & A_{1n}\\
A_{21} & A_{22} & & ...
0
votes
2answers
99 views
efficient matrix inversion problem
So I'm trying to invert a matrix of the $\begin{pmatrix}
A & B \\
C & D
\end{pmatrix}$ where $A$ and $D$ are square, $D$ is much larger than $A$, and $D$ is diagonal. $A$ $B$ and $C$ have no ...
0
votes
0answers
103 views
Difference between Marching Cube Algorithm and Iso-Surfaces?
I have always seen the two ideas together so I am not sure what makes them different...
1
vote
1answer
120 views
Can someone explain to me the relationship between primorials and factorials and how that relation can be used to compute large factorials?
What I am trying to figure out is a way to compute large factorials, !1000000.
For what it's worth luschny's computer algorithms do a very good job of it.
1
vote
1answer
138 views
Solve equation on the PC
A friend of mine asked me to help him and make a small application to solve a problem. This problem can be reduced to this equation system:
aX = Yb;
Y > c;
Y < d;
X is a whole number (X has ...
1
vote
1answer
65 views
Finding the computational complexity of an algorithm
Algorithm:
for (int i = 0; i < 2*n; i += 2)
for (int j = n; j >i; j--)
foo();
I want to find the number of times foo() is called.
...
0
votes
1answer
55 views
$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$
I must use O notation to show that:
$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$
But, I don't understand what mean: $n^{O(1)}$
0
votes
2answers
326 views
Notation : What is the meaning of the (mod n) in factoring algorithms?
Pretty much every thing is in the title, really! I'm trying to come up with an efficient algorithm to factorize large integer as an homework for a parallel programming course.
I've seen a few pages ...
3
votes
1answer
112 views
Method For Constructing Self Referential Formulas Like Tupper's
Can anyone please explain exactly how formulas like Tupper's self referential formula can be constructed?
I'll like to see the reasoning behind the derivation of such formulas and the steps required ...
