Orbis non sufficit
Friday, August 22, 2008
Wow, slow.
So, I am trying to brute force calculate some properties of the set of subgraphs on n nodes. Up to around n=5 this goes pretty well, takes less than a minute to figure my stuff out. It gets horribly bad very fast though. The thing as least runs now instead of just running out of memory and crashing. However, I built an "estimated time till completion" algorithm so I could make sure that calculations were still being performed and have encountered some unfortunate numbers.
Just my main loop, without even calculating anything about the graphs, has the following ETC(n):
Below n=4 my counter doesn't even start
n=5, ETC~0 seconds
n=6, ETC~7 seconds
n=7, ETC~7 minutes
n=8, ETC~16 hours
n=9, ETC~4000 hours
n=10, ETC~2,000,000 hours (2e6)
n=11, ETC~2,300,000,000 hours (2.3e9)
n=12, ETC~410,000,000,000 hours (4.1e11)
n=13, ETC~20,000,000,000,000,000 hours (2e16)
at which point we have to wait significantly longer than the current age of the universe, ~140,000,000,000,000 hours (1.4e14).
Note for instance that if I actually try and calculate something, the n=10 ETC (for instance) goes from 2e6 hours to 15e6 hours, or 30e6 hours if I try to calculate two things.
My program is much more robust now, it can actually calculate these things I believe, it's just too slow. Even the Monash supercomputer isn't going to help very much. It seems I must accept the limitations of this method.
With a bit of luck I might be able to do up to n=9 on a faster computer than mine, 4000 hours might drop to something reasonable.
Huzzah, a result! I'm sure this is a well known result, it's kind of neat though. Think about it.
If it isn't clear what has happened, I have taken n nodes, found all the subgraphs (undirected, no loops or double edges) and calculated their average degree (number of edges attached to a particular node is it's degree). I then averaged this number over all the subgraphs that can be drawn on n nodes, plotting this on the y-axis. I do this for n=2,3,4,5.
So, I am trying to brute force calculate some properties of the set of subgraphs on n nodes. Up to around n=5 this goes pretty well, takes less than a minute to figure my stuff out. It gets horribly bad very fast though. The thing as least runs now instead of just running out of memory and crashing. However, I built an "estimated time till completion" algorithm so I could make sure that calculations were still being performed and have encountered some unfortunate numbers.
Just my main loop, without even calculating anything about the graphs, has the following ETC(n):
Below n=4 my counter doesn't even start
n=5, ETC~0 seconds
n=6, ETC~7 seconds
n=7, ETC~7 minutes
n=8, ETC~16 hours
n=9, ETC~4000 hours
n=10, ETC~2,000,000 hours (2e6)
n=11, ETC~2,300,000,000 hours (2.3e9)
n=12, ETC~410,000,000,000 hours (4.1e11)
n=13, ETC~20,000,000,000,000,000 hours (2e16)
at which point we have to wait significantly longer than the current age of the universe, ~140,000,000,000,000 hours (1.4e14).
Note for instance that if I actually try and calculate something, the n=10 ETC (for instance) goes from 2e6 hours to 15e6 hours, or 30e6 hours if I try to calculate two things.
My program is much more robust now, it can actually calculate these things I believe, it's just too slow. Even the Monash supercomputer isn't going to help very much. It seems I must accept the limitations of this method.
With a bit of luck I might be able to do up to n=9 on a faster computer than mine, 4000 hours might drop to something reasonable.
Huzzah, a result! I'm sure this is a well known result, it's kind of neat though. Think about it.
If it isn't clear what has happened, I have taken n nodes, found all the subgraphs (undirected, no loops or double edges) and calculated their average degree (number of edges attached to a particular node is it's degree). I then averaged this number over all the subgraphs that can be drawn on n nodes, plotting this on the y-axis. I do this for n=2,3,4,5.
Friday, August 15, 2008
Reschedule
Ok, due to lack of interest ski trip on those other dates has been rescheduled to:
Sat 23rd - Mon 25th August
Still at Hotham.
There will be annoying crowds but oh well. Staying till monday will show you how much better the weekdays are.
Let me know on facebook ASAP if those days work for you, coz it's pretty soon and I therefore have book accomodation ASAP if we are going to go those days. It will be hard to find somewhere already I imagine.
Go! Make yourselves free!
For interests sake, check out my program:
(aww, it killed my formatting, but oh well)
My commenting may seem excessive, but some of it is physics commenting not code commenting. It really doesn't do much yet.
%%%%|SECTION 1------------------------------|%%%%
%%%%| BEGIN QUANTUM GRAPH GENERATION |%%%%
%%%%|_______________________________________|%%%%
%So, this is the beginning of my quantum graph spacetime generator. Firstly
%we need a general method for creating a quantum spacetime state. This will
%simply involve generating some amplitudes for edges states and calculating
%the resultant subgraph amplitudes.
%I will need two arrays in which to store the amplitudes, an "off (|0>)"
%amplitude array and an "on (|1>)" amplitude array. Each array will be of
%size nxn (each edge joins one of n nodes to another of n nodes) The arrays
%will be symmetric with zeros on the diagonal if we disallow
%directionality, loops and multiple connections between nodes.
%Here we have some input paramenters
n=3
%There will be 2^nedges subgraph basis states (nedges =
%number of edge states = 2*T(n-1), where T(n) calculates the nth triangular
%number.
nedges = T(n-1)
nedgestates = 2*T(n-1)
nsubgraphs = 2^nedges
%Begin array definitions:
a = zeros(n,n); %empty array for storing "off" (|0>) amplitudes
b = zeros(n,n); %empty array for storing "on" (|1>) amplitudes
%test amplitudes. Note that these amplitudes totally determine the graph properties
%(equal probablity, no phase difference)
a = [sqrt(0.5)*exp(4i) sqrt(0.5) sqrt(0.5); sqrt(0.5)*exp(2i) sqrt(0.5) sqrt(0.5); sqrt(0.5) sqrt(0.5) sqrt(0.5)]
b = [sqrt(0.5) sqrt(0.5) sqrt(0.5)*exp(8i); sqrt(0.5) sqrt(0.5) sqrt(0.5); sqrt(0.5) sqrt(0.5) sqrt(0.5)]
%Additionally I want these amplitudes listed in a vector in increasing order
%for later use. i.e. I need them in the form (assuming K4),
%[a12 a13 a14 a23 a24 a34...], we leave out many entries that are zero or
%are symmetric to other entries in this vector. Most efficient way to store
%the info.
a_vect = ones(nedges,1);
b_vect = ones(nedges,1);
k = 1; %Initialise a_vect and k
for i = 1:n
for j = (i+1):n
a_vect(k) = a(i,j); %store this amplitude in the kth slot of a_vect
b_vect(k) = b(i,j); %store this amplitude in the kth slot of b_vect
k = k + 1; %go to the next slot in a_vect
end
end
%I also will have an array to store the amplitudes associated with each
%subgraph basis state |g>. There will be 2^nedges subgraph basis states
%(nedges = T(n-1), where T(n) calculates the nth triangular number. Note we
%raise 2 to this power because each edge may be in one of two states). I
%need to be quite careful about defining which subgraph is which to reduce
%later confusion. In the interests of this I will here define a
%conventional ordering of edge states which can be used to categorise the
%subgraph states in a manageable way.
%The convention is best demonstrated with an example:
%|K4> = a12.a13.a14.a23.a24.a34|0>|0>|0>|0>|0>|0>+...
% = a12.a13.a14.a23.a24.a34|G0>+...
% = c0|G0>+...
%i.e if we order the states so that the first index remains constant while
%the second increases through it's range, then the first increments up and
%we repeat, then we achieve a consistent ordering of edge states and can
%assign the decimal system value of the binary number represented by the
%edge state zeros and ones to that subgraph state. We can then store the
%amplitude of that subgraph in the array position corresponding to that
%number. (Note the binary number will be read from left to right, so the
%least significant bit corresponds to the lowest ordered amplitude).
%Finally, there is no zeroth array element, so we shall store all the
%amplitudes in the index position one higher than the binary number they
%are associated with, i.e. amplitude for subgraph zero is stored in
%position 1, subgraph 1 in position 2 etc.
c_vect = ones(nsubgraphs,1); %array to store subgraph amplitudes in
for k=0:(nsubgraphs-1) %Cycle through the possible subgraphs
out = dec2binvec(k,nedges); %convert the subgraph number (k) to decimal, using as many bits as there are edge states (nedges). The decimal value is stored as a vector (out) with the least significant bit in the lowest position.
for j = 1:nedges %cycle through the entries of out, a_vect and b_vect (length is nedges)
switch out(j) %see if this bit is zero or one
case 0
c_vect(k+1) = c_vect(k+1)*a_vect(j)%; %if this bit is a zero, multiply by "off" amplitude
case 1
c_vect(k+1) = c_vect(k+1)*b_vect(j)%; %if this bit is a zero, multiply by "on" amplitude
otherwise
disp('ERROR, badness with decimal to binary conversion')
end
end
end
%Alright, this seems to work properly.
%%%%|SECTION 1------------------------------|%%%%
%%%%| END QUANTUM GRAPH GENERATION |%%%%
%%%%|_______________________________________|%%%%
%%%%|SECTION 2------------------------------|%%%%
%%%%| BEGIN GRAPH ANALYSIS |%%%%
%%%%|_______________________________________|%%%%
Ok, due to lack of interest ski trip on those other dates has been rescheduled to:
Sat 23rd - Mon 25th August
Still at Hotham.
There will be annoying crowds but oh well. Staying till monday will show you how much better the weekdays are.
Let me know on facebook ASAP if those days work for you, coz it's pretty soon and I therefore have book accomodation ASAP if we are going to go those days. It will be hard to find somewhere already I imagine.
Go! Make yourselves free!
For interests sake, check out my program:
(aww, it killed my formatting, but oh well)
My commenting may seem excessive, but some of it is physics commenting not code commenting. It really doesn't do much yet.
%%%%|SECTION 1------------------------------|%%%%
%%%%| BEGIN QUANTUM GRAPH GENERATION |%%%%
%%%%|_______________________________________|%%%%
%So, this is the beginning of my quantum graph spacetime generator. Firstly
%we need a general method for creating a quantum spacetime state. This will
%simply involve generating some amplitudes for edges states and calculating
%the resultant subgraph amplitudes.
%I will need two arrays in which to store the amplitudes, an "off (|0>)"
%amplitude array and an "on (|1>)" amplitude array. Each array will be of
%size nxn (each edge joins one of n nodes to another of n nodes) The arrays
%will be symmetric with zeros on the diagonal if we disallow
%directionality, loops and multiple connections between nodes.
%Here we have some input paramenters
n=3
%There will be 2^nedges subgraph basis states (nedges =
%number of edge states = 2*T(n-1), where T(n) calculates the nth triangular
%number.
nedges = T(n-1)
nedgestates = 2*T(n-1)
nsubgraphs = 2^nedges
%Begin array definitions:
a = zeros(n,n); %empty array for storing "off" (|0>) amplitudes
b = zeros(n,n); %empty array for storing "on" (|1>) amplitudes
%test amplitudes. Note that these amplitudes totally determine the graph properties
%(equal probablity, no phase difference)
a = [sqrt(0.5)*exp(4i) sqrt(0.5) sqrt(0.5); sqrt(0.5)*exp(2i) sqrt(0.5) sqrt(0.5); sqrt(0.5) sqrt(0.5) sqrt(0.5)]
b = [sqrt(0.5) sqrt(0.5) sqrt(0.5)*exp(8i); sqrt(0.5) sqrt(0.5) sqrt(0.5); sqrt(0.5) sqrt(0.5) sqrt(0.5)]
%Additionally I want these amplitudes listed in a vector in increasing order
%for later use. i.e. I need them in the form (assuming K4),
%[a12 a13 a14 a23 a24 a34...], we leave out many entries that are zero or
%are symmetric to other entries in this vector. Most efficient way to store
%the info.
a_vect = ones(nedges,1);
b_vect = ones(nedges,1);
k = 1; %Initialise a_vect and k
for i = 1:n
for j = (i+1):n
a_vect(k) = a(i,j); %store this amplitude in the kth slot of a_vect
b_vect(k) = b(i,j); %store this amplitude in the kth slot of b_vect
k = k + 1; %go to the next slot in a_vect
end
end
%I also will have an array to store the amplitudes associated with each
%subgraph basis state |g>. There will be 2^nedges subgraph basis states
%(nedges = T(n-1), where T(n) calculates the nth triangular number. Note we
%raise 2 to this power because each edge may be in one of two states). I
%need to be quite careful about defining which subgraph is which to reduce
%later confusion. In the interests of this I will here define a
%conventional ordering of edge states which can be used to categorise the
%subgraph states in a manageable way.
%The convention is best demonstrated with an example:
%|K4> = a12.a13.a14.a23.a24.a34|0>|0>|0>|0>|0>|0>+...
% = a12.a13.a14.a23.a24.a34|G0>+...
% = c0|G0>+...
%i.e if we order the states so that the first index remains constant while
%the second increases through it's range, then the first increments up and
%we repeat, then we achieve a consistent ordering of edge states and can
%assign the decimal system value of the binary number represented by the
%edge state zeros and ones to that subgraph state. We can then store the
%amplitude of that subgraph in the array position corresponding to that
%number. (Note the binary number will be read from left to right, so the
%least significant bit corresponds to the lowest ordered amplitude).
%Finally, there is no zeroth array element, so we shall store all the
%amplitudes in the index position one higher than the binary number they
%are associated with, i.e. amplitude for subgraph zero is stored in
%position 1, subgraph 1 in position 2 etc.
c_vect = ones(nsubgraphs,1); %array to store subgraph amplitudes in
for k=0:(nsubgraphs-1) %Cycle through the possible subgraphs
out = dec2binvec(k,nedges); %convert the subgraph number (k) to decimal, using as many bits as there are edge states (nedges). The decimal value is stored as a vector (out) with the least significant bit in the lowest position.
for j = 1:nedges %cycle through the entries of out, a_vect and b_vect (length is nedges)
switch out(j) %see if this bit is zero or one
case 0
c_vect(k+1) = c_vect(k+1)*a_vect(j)%; %if this bit is a zero, multiply by "off" amplitude
case 1
c_vect(k+1) = c_vect(k+1)*b_vect(j)%; %if this bit is a zero, multiply by "on" amplitude
otherwise
disp('ERROR, badness with decimal to binary conversion')
end
end
end
%Alright, this seems to work properly.
%%%%|SECTION 1------------------------------|%%%%
%%%%| END QUANTUM GRAPH GENERATION |%%%%
%%%%|_______________________________________|%%%%
%%%%|SECTION 2------------------------------|%%%%
%%%%| BEGIN GRAPH ANALYSIS |%%%%
%%%%|_______________________________________|%%%%
Monday, August 04, 2008
Awexome ski trip 2008
OK ppl, the time has come. We must begin planning for awesome.
Tentative dates:
Sun-tues, 24-26 aug.
Place: Buller
Price:
Probably I'd set aside about $500-$600 on the safe side. Price breakdown:
Adult:
day/lift ticket/lift ticket plus ski/snowboard hire (we may be able to hire stuff cheaper off the mountain.
2-day $184 $267
3-day $264 $372
Tertiary:
2-day $147 $213
3-day $210 $296
Tertiary students get half price lift tickets on tuesday (sorry, thought it was everyone), tho I dunno how that fits into multiday tickets, might not make much difference. Tertiary is much cheaper anyway, so if you can fake being a tertiary student (old yet apparantly valid student ID
Then there is accomodation (hopefully we can find somewhere dodgy to stay a bit cheaper, or maybe a big group thing if there are lots of us) petrol and food, so add extra money for that. Expensive I know, kinda sucks, but it is awesome to the max.
In fact, if we have more than 10 of us, which I'm thinking is likely (my sister wants to come too, plus other random hangers on and whatever) then we can get discounted group rates, 10% off adult, %20 off tertiary, which makes a pretty big difference.
Check out the group info form for buller for more details. We'll want to book that decently in advance tho, which I'll be happy to organise once we can gauge the level of interest.
Adults would drop to $334 for 3 day lift and hire, tertiary down to $296. Oh, thats the same as before. hmm. wonder what that's about. Maybe we don't get more discount for the group. Anyway it would be nicer for the adults at least.
If you have to hire waterproof jackets and pants thats like $60 extra too. Might even be worth buying cheapish stuff like that. You don't need super warm stuff, you can wear warm clothes under waterproof pants and it's fine (I wore waterproof overpants over jeans only for most of my time at Sierra and was warm. ON really cold days I wore tracksuit pants under the jeans.) Waterproof stuff is cheaper than the actual warm stuff. Anyway, that's a side issue.
As a group we can get discounted lessons too if anyone was interested in that. It can make it easier to learn. I never had any, but some people reckon lessons are good to have. Not that cheap tho.
Even if you only want to come up for say 2 out the 3 days we can still work something out. 3 days will be more epic awesome.
I know the weekdays are difficult for those of you with work (and also uni), but you'll get a lot more out of it without the ridiculous weekend crowds cramping your style. It won't be so bad while you're learning on sunday (tho lift lines will still suck) but once you start getting the hang of it on monday you'll be glad there are fewer people in the way. Especially coz most of you guys will need to spend most of your time on the easy slopes, which is where EVERYONE goes; they get crowded.
Thats enough for now. Let there be expressions of interest and discussion in the comments. We want to lock in some dates soon so we can have lots of time to prepare, especially if we want to do a group booking.
Let there be AWESOME.
Oh yeah, invite whoever you want, especially if they have contacts who can get us cheap accommodation :p.
I might look into booking the Monash cabin, I know they have one up there. I'm thinking it's pretty popular tho so I wouldn't hold my breath.
*edit: Yeah the lodge is totally booked out around that time. I'll have to remember that tho, it's pretty cheap and you don't need a group, can just go by yourself and grab a bed. Sweet.
final thing: Oh my god, how amazing is this?
That is Shishapangma, in Tibet near the Nepal border. 14th highest mountain in the world. I have to go to these places.
OK ppl, the time has come. We must begin planning for awesome.
Tentative dates:
Sun-tues, 24-26 aug.
Place: Buller
Price:
Probably I'd set aside about $500-$600 on the safe side. Price breakdown:
Adult:
day/lift ticket/lift ticket plus ski/snowboard hire (we may be able to hire stuff cheaper off the mountain.
2-day $184 $267
3-day $264 $372
Tertiary:
2-day $147 $213
3-day $210 $296
Tertiary students get half price lift tickets on tuesday (sorry, thought it was everyone), tho I dunno how that fits into multiday tickets, might not make much difference. Tertiary is much cheaper anyway, so if you can fake being a tertiary student (old yet apparantly valid student ID
Then there is accomodation (hopefully we can find somewhere dodgy to stay a bit cheaper, or maybe a big group thing if there are lots of us) petrol and food, so add extra money for that. Expensive I know, kinda sucks, but it is awesome to the max.
In fact, if we have more than 10 of us, which I'm thinking is likely (my sister wants to come too, plus other random hangers on and whatever) then we can get discounted group rates, 10% off adult, %20 off tertiary, which makes a pretty big difference.
Check out the group info form for buller for more details. We'll want to book that decently in advance tho, which I'll be happy to organise once we can gauge the level of interest.
Adults would drop to $334 for 3 day lift and hire, tertiary down to $296. Oh, thats the same as before. hmm. wonder what that's about. Maybe we don't get more discount for the group. Anyway it would be nicer for the adults at least.
If you have to hire waterproof jackets and pants thats like $60 extra too. Might even be worth buying cheapish stuff like that. You don't need super warm stuff, you can wear warm clothes under waterproof pants and it's fine (I wore waterproof overpants over jeans only for most of my time at Sierra and was warm. ON really cold days I wore tracksuit pants under the jeans.) Waterproof stuff is cheaper than the actual warm stuff. Anyway, that's a side issue.
As a group we can get discounted lessons too if anyone was interested in that. It can make it easier to learn. I never had any, but some people reckon lessons are good to have. Not that cheap tho.
Even if you only want to come up for say 2 out the 3 days we can still work something out. 3 days will be more epic awesome.
I know the weekdays are difficult for those of you with work (and also uni), but you'll get a lot more out of it without the ridiculous weekend crowds cramping your style. It won't be so bad while you're learning on sunday (tho lift lines will still suck) but once you start getting the hang of it on monday you'll be glad there are fewer people in the way. Especially coz most of you guys will need to spend most of your time on the easy slopes, which is where EVERYONE goes; they get crowded.
Thats enough for now. Let there be expressions of interest and discussion in the comments. We want to lock in some dates soon so we can have lots of time to prepare, especially if we want to do a group booking.
Let there be AWESOME.
Oh yeah, invite whoever you want, especially if they have contacts who can get us cheap accommodation :p.
I might look into booking the Monash cabin, I know they have one up there. I'm thinking it's pretty popular tho so I wouldn't hold my breath.
*edit: Yeah the lodge is totally booked out around that time. I'll have to remember that tho, it's pretty cheap and you don't need a group, can just go by yourself and grab a bed. Sweet.
final thing: Oh my god, how amazing is this?
That is Shishapangma, in Tibet near the Nepal border. 14th highest mountain in the world. I have to go to these places.
Saturday, August 02, 2008
wtrjsjsfkghkv
Urge to snowboard...rising.
The moment my scholarship money lands in my bank account, we are organising a trip. If not I'm going without you all :p.
The thought not infrequently crosses my mind of ditching life and living in the snow forever. It's not a bad thought. The snowfields are such beautiful places and they have the awesomeness of snowboarding; it'd be a sweet life. Kind of pointless I suppose, but most peoples lives are pointless anyway, so who cares? Stupid moral obligation to try and contribute to society.
Urge to snowboard...rising.
The moment my scholarship money lands in my bank account, we are organising a trip. If not I'm going without you all :p.
The thought not infrequently crosses my mind of ditching life and living in the snow forever. It's not a bad thought. The snowfields are such beautiful places and they have the awesomeness of snowboarding; it'd be a sweet life. Kind of pointless I suppose, but most peoples lives are pointless anyway, so who cares? Stupid moral obligation to try and contribute to society.
