This tag concerns computational problems central to mathematical and scientific computating. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.

learn more… | top users | synonyms

2
votes
0answers
89 views

Solving a particular system of Diophantine equations in $n$ variables (Frobenius equations)

I have a particular system of linear Diophantine equations in $n$ variables for which I need to find all nonnegative integer solutions. Specifically, they are Frobenius equations, meaning the ...
1
vote
1answer
66 views

Is there a good strategy for computing eigenspace corresponding to $1$ of a matrix with entries of trigonom

For example, say $A= \left ( \begin{matrix} \cos x & -\sin x & 0 \\ \cos y \sin x & \cos x \cos y & -\sin y \\ \sin x \sin y & \sin y \cos x & \cos y \end{matrix} \right)$. ...
-2
votes
2answers
81 views

Is there any good strategy for computing null space of a matrix with entries $\cos x$ and $\sin x$?

For example, say $A= \left ( \begin{matrix} \cos x & -\sin x & 0 \\ \cos y \sin x & \cos x \cos y & -\sin y \\ \sin x \sin y & \sin y \cos x & \cos y \end{matrix} \right)$. ...
2
votes
1answer
347 views

Numerical Integration over 2D Regions with Discontinuous Functions

I've run into a tricky problem, and I haven't really thought up a good solution. I have to compute many integrals of the form $$\iint\limits_{B((x_k,y_k),\epsilon))} f(x,y) dy dx$$ where ...
0
votes
0answers
36 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
4
votes
4answers
328 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
2
votes
2answers
106 views

Uniform grid on a disc

Do there exist any known methods of drawing a uniform grid on a disk ? I am looking for a map that converts a grid on a square to a grid on a disk.
2
votes
1answer
104 views

What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
6
votes
2answers
181 views

What is the average weight of a minimal spanning tree of $n$ randomly selected points in the unit cube?

Suppose we pick $n$ random points in the unit cube in $\mathbb{R}_3$, $p_1=\left(x_1,y_1,z_1\right),$ $p_2=\left(x_2,y_2,z_2\right),$ etc. (So, $x_i,y_i,z_i$ are $3n$ uniformly distributed random ...
2
votes
0answers
34 views

Computing a particular finite set of quaternion matrices.

Let $B = \left(\frac{-1,-11}{\mathbb{Q}}\right)$ be a choice of quaternion algebra ramifying at $11$ and consider the maximal order ...
0
votes
0answers
124 views

Effects of numerical integration stepsize on impulse inputs (e.g., delta function)

Some models of neurons treat synaptic input (from other neurons) as a single impulse, such as the Dirac delta. But doesn't this make the magnitude of that impulse a function of numerical integration ...
0
votes
1answer
34 views

Find all points where the gradient of a high-dimensional function are equal to zero in some domain, numerically

I was wondering if anybody was aware of a numerical method to find all points where the gradient of a high-dimensional function are equal to zero in some domain. Thanks
5
votes
1answer
373 views

Cylinder-ray intersections equation

I found an article involving infinite cylinder-ray intersections, and I don't know how they develop this equation: $$(q - p_a - (v_a, q - p_a)v_a)^2 - r^2 = 0$$ In the end of the first page I quote: ...
1
vote
2answers
244 views

Space spanned by matrices

I have a set of 5 by 5 matrices, M1,M2,...,M19 ,M20. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should approach the ...
0
votes
0answers
66 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 ...
1
vote
0answers
16 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$, ...
4
votes
3answers
2k views

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 ...
4
votes
1answer
54 views

About parallel time computation

I am studying a paper where it is mentioned that Newton iteration may be used to compute the inverse of $n \times n$, well- conditioned matrix in parallel time $o(\log^2n)$ and that this computation ...
5
votes
3answers
686 views

What free software can I use to solve a system of linear equations containing an unknown?

Question: What free software can I use to solve a system of linear equations $M\mathbf{x}=\mathbf{y}$ where the entries of $\mathbf{y}$ vary with an unknown quantity $n$? Presumably I could do ...
1
vote
0answers
128 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: ...
9
votes
2answers
228 views

Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ...
6
votes
1answer
520 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 + ...
0
votes
1answer
97 views

how can I find the following problem using laplace transform?

For example here is the problem: $(t^2 \cos{\omega t})u(t)$ I have to find it using laplace transform; here is what I think it is, I have $t^2$$(\cos{\omega t})u(t)$ which I think I can solve them ...
1
vote
6answers
738 views

What is the value of $2^{3000}$ [closed]

What is the value of $2^{3000}$? How to calculate it using a programming language like C#?
12
votes
1answer
161 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 ...
1
vote
2answers
119 views

How are 10-20 digit multiperfect and hemiperfect numbers efficiently computed?

This numericana item on multiperfect and hemiperfect numbers contains some impressively enormous numbers. How were these actually computed ? The associated OEIS pages (A007691 & A159907) just ...
4
votes
1answer
227 views

What is the fastest computational graph theory package?

What is the fastest computational graph theory package with respect to executing algorithms and computing graph theoretic data? I am aware of this related question, which requests graph theory ...
1
vote
1answer
86 views

How do I determine if two of my software's representation of algebraic numbers are equal?

I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, ...
0
votes
2answers
60 views

Does rationalizing the denominator lead to more or less round-off error?

I evaluated $\frac{1}{\sqrt{2}}$ and $\frac{\sqrt{2}}{2}$ in Matlab, and got a slight difference: $0.707106781186547$ and $0.707106781186548$, respectively. Which is more accurate, the one with the ...
1
vote
1answer
57 views

Matrix completion: supplementary questions

Continuation of the question here, what is going to happen if we change the some of the conditions. I write it as a quote from here and change the appropriate places which are underlined: I need ...
2
votes
3answers
135 views

Drawing graphs (vertices and edges) with or without technology

Given a collection of vertices $V$ and a collection of edges $E \subseteq V\times V$, is there an algorithm or program that will allow you to draw a nice graph? The placing of the vertices is very ...
-1
votes
1answer
226 views

Best graphing program for Mac or PC?

I just bought the highest end iMac, with a student discount, of course, and was wondering what is the best graphing program out there. A program that can graph any equation that I throw at it AND one ...
3
votes
2answers
411 views

How to get the minimum angle between two crossing lines?

I'm not a student, I'm just a programmer trying to solve a problem ... I just need the practical way to calculate the smallest angle between two lines that intersect. The value, of course, must always ...
1
vote
1answer
126 views

Matrix completion

I need to find an algorithm (if exists) of the following matrix completion problem. I need to construct $n^2$ positive semi-definite matrices, say $\{P_i\}_{i=1}^n$. Entries of these matrices are ...
1
vote
1answer
524 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 ...
6
votes
3answers
211 views

Mathematical Limitations of Computer Experiments

One problem that has always bothered me is the limitations of computers in studying math. With a chaotic dynamical system, for example, we know mathematically that they possess trajectories that never ...
1
vote
1answer
67 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
votes
1answer
98 views

Qubit state finding [closed]

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
2answers
115 views

Can product of all pairwise sums be computed faster than the naive method?

Let $S$ be a set of integers. $|S|=n$. Can we find the product $\prod_{a,b\in S} a+b$ faster than naively add all pairs then multiply them one by one? By faster, I mean use less than $O(n^2)$ ...
1
vote
1answer
71 views

How to find a close form expression in terms generating functions for the triple summation

Given $$\sum\limits_{i=0}^\infty a_i z^i=A(z)$$ and $$\sum\limits_{i=1}^\infty b_i z^i=B(z)$$ and $$\sum\limits_{i=0}^\infty c_i z^i=C(z)$$ Find $\sum\limits_{i=1}^\infty\sum\limits_{j=0}^\infty a_j ...
6
votes
9answers
7k views

Fastest Square Root Algorithm

What is the fastest algorithm for finding the square root of a number? I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release ...
2
votes
1answer
61 views

Amicable numbers

Def: a pair natural numbers $a$, $b$, $a\ne b$ are an Amicable pair if $\sum_{d|a,a\ne d}d = b$ and $\sum_{d|b, b\ne d}d = a$. Ok. So I'm trying to optimize a calculation for finding the number of ...
3
votes
3answers
637 views

Understanding recursive definitions of a language.

I am having difficulty understanding the recursive definition of a language. The problem asked how to write this non recursively. But I want to understand just how a recursive definition of a ...
0
votes
1answer
43 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 ...
5
votes
1answer
1k views

A search for integers which can be written as a sum of two squares in multiple ways

As part of a number theory hobby project, I'm looking for a computational way to enumerate all integers $n$ which can be written as a sum of two integer squares in three or more ways. The range of ...
7
votes
1answer
148 views

Fractional part of exp(x)

I have a real number $x$ (for concreteness, say $10^4<x<10^6$) and would like to find $e^x-\lfloor e^x\rfloor$ to reasonable precision (10-20 decimal places). What is the most efficient method? ...
2
votes
0answers
250 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
2answers
101 views

Number of ways to move 1 or more elements from one list to the previous list until one list remains

Given N elements, divided into at most N groups, which are then labeled 1 thru N, move all of the elements into the group labeled 1. By moving 1 to all of the elements, in group i to i-1. This means ...
0
votes
2answers
1k views

Questions that can be solved using Excel.

I recently started to realize that Excel is a powerful tool that can solve many problems. What interesting mathematics problems are there can be solved using excel? I am looking for a set of ...
1
vote
1answer
153 views

Where does the input x in Turing Machine subroutines come from in solving reductions to undecidable problems?

I'm taking an introduction to computation theory class and we went over the chapter on undecidable problems and proving undecidability through reductions. I can't seem to grasp some of the simplest ...