Computational mathematics involves mathematical research in areas of science where computing plays a central and essential role, emphasizing algorithms, numerical methods, and symbolic methods.
7
votes
1answer
205 views
Krylov-like method for solving systems of polynomials?
To iteratively solve large linear systems, many current state-of-the-art methods work by finding approximate solutions in successively larger (Krylov) subspaces. Are there similar iterative methods ...
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 ...
2
votes
1answer
87 views
Factoring short intervals
There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$.
...
1
vote
1answer
78 views
Minimizing mean squared error
I want to find a $d$ that minimizes the value of the expression below. I think the first step is to find the derivative w.r.t. $d$ (is that correct? If not, what is the first step?). If so, I'm having ...
1
vote
1answer
35 views
Discrete numerical derivative with respect to d/d(n*x)
How can I generate a stencil for a d/d(n*x) operator?
I am writing a program that needs a method to calculate line derivatives in an image. If we want to calculate the simplest forward derivative ...
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
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, ...
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 ...
0
votes
1answer
39 views
Probability : Dividing a list into 2 classes
I have a list of integer numbers ($n$). I am dividing it into two parts $n_1$ (smaller) and $n_2$ (bigger) such that the length of $n_1 \ge a*n$; $a$ is positive and $a \lt 0.5$. What is the ...
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 ...
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)}$
19
votes
0answers
295 views
Computing (on a computer) the first few (non-trivial) zeros of the zeta function of a number field
If $K$ is a number field, whose Galois closure over the rationals has degree 24 or so, and whose discriminant is around $163^4$, then what is a numerically efficient way of computing the first few ...
5
votes
0answers
49 views
Evaluation of a slow continued fraction
Puzzle question... I know how to solve it, and will post my solution if needed; but those who wish may participate in the spirit of coming up with elegant solutions rather than trying to teach me how ...
4
votes
0answers
142 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 ...
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 ...
3
votes
0answers
44 views
How to find an expression whose value is 190
Given a set of numbers (in this case):
3, 7, 7, 100, 50
Either:
prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + ...
2
votes
0answers
51 views
+50
Derivative of Associated Legendre polynomials at $x = \pm 1$
I'm creating meshes for spherical harmonics, and I need a normal at a given point. Whenever I'm at the poles, $\cos{\theta} = \pm 1$, and I do not know how to find the derivative there. All the ...
2
votes
0answers
77 views
How to convert a hologram into an image?
Suppose one knows in full detail the phase and intensity of monochromatic light in a plane. This is basically what a hologram records, at least for some section of a plane. By using this as the ...
2
votes
0answers
121 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 ...
2
votes
0answers
46 views
is there a computationally efficient formula for computing the mutual information between two continuous variables?
I need to compute the mutual information between two continuous variables. Below is an equation shown to compute the mutual information between a variable $X$ and $Y$.
$I(X;Y) = \int_Y \int_X
...
2
votes
0answers
240 views
Clarification on different types of solutions: analytical, closed form, iterative, algorithmic,
When doing computation, there are different types of solutions: analytical, closed form, iterative, algorithmic, exact, approximate, ... (there are probably more than I just listed and please don't ...
2
votes
0answers
160 views
Optimal division sequences for divide-and-conquer algorithms
Say we have a discrete data set of some size, and we can use a recursive divide-and-conquer algorithm to process the data in some way (an FFT for example). The naive solution is, say, $n^2$ in ...
1
vote
0answers
9 views
Tools for optimizing asymptotic bounds.
Is there any tool for this task ?
Given the asymptotic bound in term of $n$ and other paramaters $t_1,\dots,t_r$, then return the value for each $t_i$ which optimizes the expression in term of $n$, ...
1
vote
0answers
35 views
Qubit state finding
Suppose we have two qubits in the state $x|00\rangle+y|11\rangle $.
What is the resulting state of the second qubit in that case? Use and to denote and respectively.
1
vote
0answers
20 views
Model to reward adaptative communication
I'm currently working in different simulations focused on the study of artificial evolution of communications in robots, and I have stumbled against the problem of its mathematic formulation.
The ...
1
vote
0answers
89 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 ...
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 ...
1
vote
0answers
82 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 ...
1
vote
0answers
49 views
lower bounds for maximum computing times for integer factorisation
Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
1
vote
0answers
83 views
calculating multivariable integrals
I having a look at how to calculate using PC a multivariable integrals.
I am reading about the Quasi Montecarlo methods using the following
(t, m, s)-Nets and (t, s)-Sequences
Faure sequences
My ...
1
vote
0answers
56 views
Computing relations on the columns of a matrix
Given an $m\times n$ (with $n>m)$ matrix $M$ over a polynomial ring $R=k[x_1,...,x_n]$, suppose that every column of $M$ is an $R$-linear combination of $m$ specified columns. I would like to ...
0
votes
0answers
13 views
Constrained computational optimization of a functional of a vector valued function.
I am trying to increase the efficiency of a program I have written that must run in real time. I am asking this question in a broad sense, since I'm not sure what tools are available to me.
I am ...
0
votes
0answers
44 views
Simpson's rule characteristics
I just wanted to ask a quick question in regards to simpson's rule for integration. I have been reading up on the trapezoidal rule, and have found the notations and have an understanding such that:
...
0
votes
0answers
59 views
Drawing finite state machines based on regular expressions
I have problems drawing the following finite state machines which use the {0,1} alphabet:
Are these DFAs or NFAs? How to determine the latter?
Tyvm for your time and help!
0
votes
0answers
48 views
Solving an overdetermined system of inequalities using null-space arguments
The solutions to a linear system of equations:
$$A\cdot x = b$$
(where $x$ is a $(n\times 1)$ column vector, $b$ is a $(m\times 1)$ column vector and $A$ is $(m\times n)$ matrix)
can all be ...
0
votes
0answers
36 views
Function design and Super-Symmetry Test Requirements
I request everyone concerned to give a serious thought and respond.
If you are asked to design two independent functions say S() and P() and should satisfy the following conditions:
There will be ...
0
votes
0answers
202 views
Simple Lanczos algorithm code to obtain eigenvalues and eigenvectors of a symmetric matrix
I would like to write a simple program (in C) using Lanczos algorithm. I came across a Matlab example which helped me to understand a bit further the algorithm, however from this piece of code I can't ...
0
votes
0answers
69 views
How to make normalized cross correlation robust to small changes in uniform regions
the problem is described below:
Given 2 sets of data: A= { 91 87 85 85 84 90 85 83 86 86 90 86 84 89 93 87 89 91 95 97 91 92 97 101 101 },
B = {133 130 129 131 133 136 131 131 135 135 133 133 133 ...
0
votes
0answers
60 views
graphing a differential equation using RK4 (making a slider graph in Excel)
So I'm graphing a system of nonlinear differential equations for my Math class and I've begun to calculate the values in Excel using Runge Kutta 4. The system includes a variable "b" that I can change ...
0
votes
0answers
16 views
Show that for every deterministic algorithm ALG, there is some scenario in which the total distance John’s trucks traverse under ALG is 3OPT
There are 3 popular beach resorts, A, B, and C, which reside on a line:
A-----(1km)-----B-----(1km)------C.
The distances between the ...
0
votes
0answers
108 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 ...
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
...
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 ...
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 ...
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 = ...
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 ...
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 ...
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...
