Thursday, March 27, 2014

Different parametric equation for a circle

I found this one:
an animation:

I found it by using the first couple of terms for the power series of sine and cosine, and making that the function for my x and y values, dividing each by the magnitude of x and y together. Then rotating the function and simplifying.
So all the points are exactly on the unit circle, but I noticed it doesn't go around always at the same speed, for example t=.5 or -.5 gives x value ~.2626 instead of 0. I'm looking at whether one could substitute in a function s for t that would make for even speed around the circle...

Tuesday, March 18, 2014

Gaussian Perturbation Optimization

This type of optimization I'll be discussing is meant to be good for very quickly finding a close to optimal solution to an optimization problem, and not suffer from becoming stuck at a local optimum.
As an example problem I'll take trying to maximize the total pairwise distance between a collection of points on a sphere by moving the points anywhere on the sphere.
First start with any random starting state:
These are in spherical coordinates
points = [[0,0],[1.5,0],[3,0], [2, 1], [3,2], [1,5]]
My algorithm does the following:
1. Perturb* the points to get newpoints
2. If the perturbed points have a higher pairwise total distance make points=newpoints
3. repeat the above over a certain number of iterations, I'll use 1000.

*Perturb: By perturb I mean to change the value of a variable to a new value determined by a Gaussian distribution with mean of the original value and deviation in this case .1.
After 1000 iterations this algorithm gives (rounded to the nearest 100th:
final = [[2.98, 0.42], [0.02, 5.64], [0.027, 5.88], [0.16, 0.22], [0.05, 2.84], [3.12, 5.62]]
with a total pairwise sum of distances of 27.66
It is known that the best that can be done is vertices of an octahedron which has a total pairwise sum of distances of: 28.26, so this algorithm came within 2% of the best possible value in much less than a second in python.

**Reasoning behind the algorithm**
The reason the algorithm perturbs the points according to a gaussian distribution is that it will generally look at values for the variables close to where the last good value was but at the same time it will occasionally try values quite a ways from the last best value, this has the effect of both generally fine-tuning the best known value but also avoids getting "stuck" in local maximums.

It's possible to run the algorithm for longer like when I run it for 1,000,000 iterations it came to 28.1 out of 28.2 possible, but most of the improvement is early on so I think it's best used to get close quickly.

It's kind of interesting to look more in depth, starting from the exact worse solution:
points = [[0,0],[0,0],[0,0], [0, 0], [0,0], [0,0]]
1 after just one perturbation
4 after four
[[3.141504678216728, 5.578547112469853], [0.0035838527843349106, 6.106448209218512], [3.1264686990942385, 0.27331447965308603], [0.006630475839969886, 5.600804904080315], [0.0379240041525053, 0.3160069253736454], [3.13340891247032, 6.14277187932977]]

So there is a very long tail of improvements but they get more and more expensive as far as iterations.

Thursday, March 13, 2014

Using the maximized cm from last post to check for isomorphism

I was just checking a few cases to see whether the algorithm from the last blog post works in practice. Here are two graphs:
Here are the two connectivity matrices. The first is rows a-j have a 1 if they are connected to a vertex a-j. And similarly for the second.  :
When I run my program on both of these above matrices to write the maximized matrix they both come out to:

So clearly the two graphs are isomorphic. I just still don't know whether this always works, but it is very fast and there can't be false positives so it might be good as a first check. 

Monday, March 10, 2014

Maximizing a connectivity matrix

For every simple graph like:
There is a connectivity matrix associated, for the one above with the labeling given it is:

The rows and columns correspond to the letters given in the graph, the first row signifies that A is connected to B, D, F, and G. The second row expresses the connections for B, etc down to row G. 

My idea is to put an ordering on connectivity matrices of the same dimension as follows: the top left cell of both matrices A[0,0] and B[0,0], if A[0,0]  is greater than B[0,0] then connectivity matrix A is greater than B. also if A[0,0] is less than B[0,0] then B is greater than A. if the two are equal, then move to the next cell A[0,1] and B[0,1].
2. Continue going across rows and then wrapping around to the next column until either one matrix is shown to be greater than the other or every cell is exactly the same, in which case A=B.  

Considering a connectivity matrix A, there is an operation I will call a relabeling that consists of swapping both Row I with Row J and Column I and Column J. For example looking at the connectivity matrix above, I could swap row 1 and row 3 and also column 1 and column 3 to get:

I call this relabeling because this is the connectivity graph you would get if you swapped what are called vertex A and vertex C in the original graph and made a connectivity matrix from that graph. A graph is still essentially the same graph under any relabeling. 

It can be seen that under the ordering of connectivity matrices I described CM2 > CM1. This is because comparing across rows and down columns the first 4 values are the same  0101, but the next value of CM2 is 1 and only 0 in CM1. 

So a connectivity graph is maximized if no relabeling or sequence of relabelings can make it greater under the ordering. Then two graphs are isomorphic if and only if their maximized connectivity graphs are the same. 
There might be many algorithms for maximizing a connectivity matrix, from here on I'll be using this conjecture:
Conjecture: A connectivity matrix is maximized if and only if it can not be made greater under any single relabeling operation. 
I can't really even think whether this is likely to be true or not, but first I will describe an algorithm that assumes it is true. 
1. Look through every pairwise combination of possible relabelings and make the relabeling if the new  connectivity matrix is greater. 
2. Repeat 1 until you reach a state where no relabeling makes the graph greater. 
For this connectivity matrix the program I wrote gives:

This one can't be made greater by any single relabeling proven through exhaustion. Remember in this graph there are no vertices connected to themselves so the identity row is all 0's. I think in this case this is the maximum for any type of relabeling of the graph, but I still haven't proven that this algorithm always results in the maximum under any type of relabeling. 
The nice thing about this method is it doesn't assume a binary matrix, all these 1's and 0's could just as easily be any numbers, possibly negative or non-integer, representing weights or directedness or any other feature of a graph.

def relabel(cm, i, j):
    cm2 = []
    for r in range(0, len(cm)):
        row = []
        for s in range(0, len(cm[0])):
    temp = cm2[i]
    cm2[i] = cm2[j]
    cm2[j] = temp
    for r in range(0, len(cm2)):
        temp = cm2[r][i]
        cm2[r][i] = cm2[r][j]
        cm2[r][j] = temp
    return cm2
def greater(cm, cm2):
    for i in range(0, len(cm)):
        for j in range(0, len(cm[0])):
            if cm[i][j] > cm2[i][j]:
                return True
            elif cm[i][j] < cm2[i][j]:
                return False
    return False
def maximize(cm):
    nobetter = False
    for i in range(0, len(cm)-1):
        for j in range(i+1, len(cm)):
            cm2 = relabel(cm, i, j)
            if greater(cm2, cm):
                return cm2, nobetter
    nobetter = True
    return cm, nobetter
cm = [[0,1,0,1,1,1,0],[1,0,1,1,1,0,1],[0,1,0,1,0,1,1],[1,1,1,0,1,0,1],[1,1,0,1,0,1,0],[1,0,1,0,1,0,1],[0,1,1,1,0,1,0]]
nobetter = False
for i in range(0, 10):
    cm, nobetter = maximize(cm)
    if nobetter == True:

Saturday, March 8, 2014

Graphst as a Left Recursive Context Free Grammar

Considering a graph such as:
I noticed that you can write the problem using rewriting rules (for this graph for example):

And so on where every letter can be replaced by a vertex connecting to it and itself, left recursively. 
So a Hamilton circuit for this graph could be generated following the rules like so:
b -> aB
a -> dA
d -> gD
g -> fG
f -> eF
e -> cE
c -> bC

Writing graph problems as Context Free Grammars and in this case left recursive ones gives immediately many useful theorems. See:

For example many problems about Context Free Grammars are undecidable in the general case.

Wednesday, March 5, 2014

Direction of vector function

So I wanted a function that goes from 0 to 2*pi and corresponds to the direction a vector is pointing on the plane. It was hard to do the first few ways I thought of with complex exponentials and arcsins and things of that nature, so I settled for a quadratic approximation. I picked the 9 integer points corresponding to the -1..1 x and y values of the vector and interpolated through what each pair should return. This is what I came up with:

So you have a vector: And you scale it by magnitude:
Then you plug these two components in the first function I listed as x and y:
And 1.211*pi looks pretty reasonable for these points.

Tuesday, March 4, 2014

A good way to measure Pi the ancients didn't discover.

It was well known to the Ancient Greeks that the circle constant was pi, but they didn't know very well what it's value was, only the first couple digits. I found a way they could have known it to quite a bit of accuracy, scientifically.
You basically just measure how many drops of water completely cover the bottom of a cup with a certain radius , and divide it by the number of drops that cover the bottom of a cube with that radius. This works because out of a dropper the average volume of a drop stays the same. And it's easy to tell how many drops because you go until there are no dry spots.
It doesn't really matter what units of measurement you use because when you divide equations for a volume of a cup and a volume of a cube, the lengths drop out and you are left only with pi. You could start by finding the volume in drops of something small, and maybe find that it could hold a hundred drops until the bottom was completely wet. Then measure something larger with how many of those plus how many drops something larger holds.  Work your way up to your cup and cube this way.
You could find that the cup would hold 1227184.6 drops and the cube 390625 which would give pi as 3.14159104 which is accurate to 6 digits, this would correspond to a 25 inch cylinder and cube dish. But you probably wouldn't be that accurate, Suppose you were off by 20 drops for each, you would still get 3.14138 or 3.1418 depending on which way you were off. And you can do the experiment any number of times and take the average to improve precision.

Language as a Cover Math

The convention of a cover math is to use lower case letters as constants, upper case letters as operators, Greek letters as variables, any combination of which is an expression symbolized by an arabic number or Greek number for a variable expression, and can be rewritten under certain rules.
Suppose you have certain constants that you symbolize with lower case letters:
the room = r
the blue ball = b
the brown box = x
the red ball = y
the green pyramid = p
the table = t

and you have certain operators you symbolize with upper case letters:
is inside of = I
is outside of = O
is on top of = T
is underneath = U
is next to = N
and = A

And you have certain axioms about the system that appear as rewriting rules, using greek letters alpha, beta etc for variables that can take the value of any constant.
The inverses say for example if an object is inside another object then the second object is outside of the first. The transitives say for example if an object is on top of another object and that second object is on top of a third than the first is on top of the third. The one under other is just that if two things are on top of another than the two are next to each other.
Those under expressions say if you end up with two expressions that are identical with an and in between, you can rewrite it as just one. And the second says if you have two expressions, you can combine them with an AND to get a third.

Now we have to add to those descriptive axioms describing our situation...
These say for example "the blue ball is inside of the brown box".
And from these many statements can be proven. We can find that the blue ball is inside the room for example , even though not explicitly stated, by adding 1 and 2 together with A by the last rule,  and then using the transitive axiom for "is inside of".
We could ask a proof machine whether "the red ball is next to the brown box" for example and it could see whether it was deducible from what it was given.

Sunday, March 2, 2014

Content design as a system of equations

As a basic example, suppose all the content on for example a web page was presented in rectangles. We might have a largest rectangle called Page that was to have all other rectangles on it in a hierarchy.
First we define the hierarchy with a set definition:
[rectangle Page[rectangle Left[text LeftTitle, text Blurb, picture Stockfoto], rectangle Right[text MainText]]]
See there are various types that would be supported, above there are text, picture ,and rectangle elements. The hierarchy is unambiguous through the children of a type being listed inside brackets, possibly nested after the type name.
Now we need to give some information about how we want everything arranged. We can set variables for the width and height of the page:
width = 1.0
height = 1.0
offset = .05
Page.coord = [[0,0],[width, height]]
All types have certain built in data structures, above the rectangle variable coord sets the top left and bottom right of the rectangle named Page.
Left.coord = [[offset, offset], [width/2.0, height - offset]]
It's possible to use references to variables inside a call to coord. Later on we could change width and height in one place to a certain number of pixels, and change offset to whatever we'd like and it would change everything about the page. = = + offset
LeftTitle.topleft = [Left.topleft.x,]
Here we use a call to Left's center variable, which can be inferred by the program from the coordinates of Left, and refer to the x coordinate within the center to set the LeftTitle's center's x coordinate at the same value. Because that is the center of LeftTitle, the bottomright will be be inferred from where the center is and where the top left is.
Blurb.topleft = [LeftTitle.topleft.x + offset, LeftTitle.topleft.y+offset]
Blurb.bottomright = [Left.right.x - offset, Left.bottomright.y*(1/3)]
Indicating we want the blurb box to go down to 1/3 of the way down the page.

Notice now that we are relating variables with equations, the program will eventually solve these equations and certain other automatically generated equations for the unknown variables. This is how the inferences are working behind the scenes. An automatically generated equation for rectangle for example is: = [(rectangle.topright.x - rectangle.topleft.x)/2.0, (rectangle.bottomleft.x - rectangle.bottomright.y)/2.0]

So hopefully the program parsing this will upon solving the equations, either produce the page or return that certain variables that are still free in the equations or that there is no solution for the variables given the criteria, at which point the user can try to add more information or change things until they get the layout they want.

So this example above might end up like:


I think this would work a lot better than the present ways for laying out content, because it can infer many variables without being explicitly told them, but it doesn't try to do too much automatically like layout systems I've used before. For example some systems have commands to try and automatically center things but sometimes that conflicts with one of the three different systems for automatically doing the padding around the content and so on. It is generally just a mess. 

Del operator in approximation matrix form

Suppose you have a grid of values A, like here the t could be temperature over a surface...

I found this matrix that relates to the del operator in physics as follows:
For higher orders of del such as the Laplacian:
It is a recursive application of the first rule. 
where G is:
This G matrix could be in any number of dimensions, the positive and negative 1/2*delta terms would just surround the identity row through that higher dimensional matrix.

To see why the formula listed works see that A*G is:
See that for a small value of delta, this is an approximation for the gradient in the x direction, that the value of an interior cell is half the difference of the cell on the right and the cell on the left divided by the delta, unless the cell is on the left or right edge, in which case it treats the cell to the left or right respectively as 0.
Similarly G(transpose) *A is the gradient in the y direction.

So the sum of the two is the del operator or the sum of the gradient in the x and y direction of A.