Computational mathematics involves mathematical research in areas of science where computing plays a central and essential role, emphasizing algorithms, numerical methods, and symbolic methods.

learn more… | top users | synonyms

5
votes
1answer
128 views

What's the best way to detect an algebraic number?

Suppose you calculate the first few (dozen, hundred) digits of a number which you believe to be a rational number. You can calculate the continued fraction for the number and truncate after a large ...
0
votes
1answer
2k views

Plot Y-Range on Mathematica

I have a plot that I would like to slightly manipulate in Mathematica. Here is the code I am entering: Plot[{x, 2^x, log_2(x)}, {x, -1, 3}] As you can see $x$, $2^x$, and $log_2(x)$ are all ...
17
votes
5answers
853 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
0
votes
1answer
517 views

Area of Union of n circles

I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the ...
1
vote
1answer
533 views

double exponential point smoothing - what do alpha and gamma do? What is “trend”?

I have some code that does double exponential point smoothing. In addition to the points to be smoothed, it accepts two inputs as "alpha and gamma" values and outputs something called "trend" in ...
2
votes
6answers
752 views

Gödel's Proof as a proof strategy for P = NP or P != NP

I have had this thought for quite a while. Gödel proved the incompleteness of arithmetic by creating a one-to-one correspondence with a number and certain numerical relationships to create a statement ...
3
votes
2answers
317 views

Graphical-entry knot theory program for Mac?

Is there a good program that runs on Mac OSX, which has a graphical interface for inputting knot or link diagrams, and calculates standard invariants like the Conway and Jones polynomials? I have ...
4
votes
1answer
310 views

Computing with ideals: over $K$ or over $\mathbb{Q}\subseteq K$? does it matter?

I'm beginning to learn to use SINGULAR, the computer algebra system (CAS) for commutative algebra. NOTATION: If $K$ is a field of characteristic $0$, then $\mathbb{Q}\subseteq K$; otherwise ...
1
vote
2answers
144 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
1
vote
0answers
69 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 ...
2
votes
0answers
339 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
244 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
94 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 ...
4
votes
1answer
1k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...
23
votes
3answers
6k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
1
vote
1answer
200 views

Structure and Formula encoding for Turing Machine

During my study of Finite Model Theory I found that usually purely relational structure say $\mathcal{M} = \langle A, R_1,\ldots,R_k \rangle$ are encoded as ...
1
vote
2answers
261 views

System of linear equations, resulting from a weighted graph. How to solve this numerically?

We have a problem that leads to a system of linear equations which has to be solved numerically. There are thousands of algorithms to solve linear equations, but I haven't found any that fits our ...
9
votes
1answer
577 views

How else can we be nauty?

The graph canonical labelling package nauty is widely regarded as one of the best (if not the best) around. Unfortunately, it's quite a large package, and making a GPU version seems to be a highly ...
2
votes
1answer
93 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$. ...
2
votes
2answers
255 views

Uniform Load on an Elastic Bar

One applied math question talks about an elastic bar with a displacement equation $du^2/dx^2 = 1$ for a uniform load and fixed on both ends. I solved this using the Toeplitz matrix K and u comes out ...
11
votes
1answer
291 views

Constructing a finite field

I'm looking for constructive ways to obtain finite fields, for any given size $q=p^n$. For example, I know it suffices to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (and then ...
3
votes
1answer
197 views

Finding all results of a permutation group on a set

Given a finite group $G < Sym(\Omega)$; $\Omega$ finite, and $X \subset \Omega$, I can define a by the function $H(g) = \{x^g \| x \in X\}$ for each $g \in G$. Of course, each $H$ has the same ...
6
votes
2answers
379 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
8
votes
2answers
1k views

How to check whether an ideal is a prime (or maximal) ideal?

I have a ring $R$ which is known to be a Dedekind domain, but not necessarily a Euclidian domain, and a nonzero ideal generated by one or two elements in this ring. How can I check if this ideal is a ...
23
votes
1answer
443 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 ...
1
vote
0answers
60 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 ...
3
votes
1answer
101 views

Find $k^{th}$ root of $M \in GL(n,F_2)$

Given $M \in GL(n,F_2)$ which is known to have a $k^{th}$ root. How can I find a root algorithmically? Can I find all roots? Other than being invertible and having a $k^{th}$ root I know nothing of ...
5
votes
3answers
399 views

Calculate $\pi$ in an arbitrary base, to arbitrary precision

I need to calculate $\pi$ -- in base: 4, 12, 32, and 128 -- to an arbitrary number of digits. (It's for an artist friend). I remember Taylor series and I've found miscellaneous "BBP" formulas, but so ...
9
votes
1answer
248 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 ...
2
votes
1answer
91 views

Decision procedure for the problem of regular expression equivalence with not

As stated in the title, I need a decision procedure for the problem of regular expression equivalence with not. Wikipedia states the problem is in the NONELEMENTARY complexity class. All I really ...
10
votes
2answers
869 views

How do I prove the partial denominators formula of the Bauer-Muir transformation of a generalized continued fraction?

Notation: $b_{0}+\underset{n=1}{\overset{\infty }{\mathbb{K}}}\left( a_{n}/b_{n}\right) $ is the Gauss Notation for generalized continued fractions. Description of the Bauer-Muir transformation ...