Read posts about math science

January 8

prentententoonstelling (eccentric squares (Kuya)) by noel

jin got me looking into mc escher stuff. the one below, prentententoonstelling was of particular interest to some mathematicians in the netherlands:



they wrote a paper that investigates the math behind the original lithograph, as well as (with a computer assist here and there) extrapolates what would have been in the central white hole which escher left blank.

the first thing they did was map the from curved image space back into a straight "real" space. the entire image tile is not recoverable, but one thing to note is that the image contains itself (see the link). the dutch call this recursive imaging a droste effect.

next, they had an artist fill in the missing details from the various resolution versions of the original image.

they then applied a transformation (a complex logarithm) to create a doubly periodic version of the image utilizing the different resolution representations.

finally, they added shades of gray.

the movies below result from applying different rotations, scalings, and complex exponential mappings on the resultant image. from there, they can look into the image the way escher intended, but was never fully able to realize:




Posted in: math science , pictures
September 27

super duper computing (eccentric squares (Kuya)) by noel

my job approved my request to go to the 2007 supercomputing conference. helping my cause was the fact that my > 80 CPU distributed monte carlo simulation is taking on the order of a week to run for some of our "we needed it last week" data.

as is evidenced by my recent reading list, i'm interested in applying GPUs to some of our large scale computational problems. i figured this tutorial session would be useful:

High Performance Computing on GPUs with CUDA

Abstract:
NVIDIA’s Compute Unified Driver Architecture (CUDA) platform is a co-designed hardware and software stack that expands the GPU beyond a graphics processor to a general-purpose parallel coprocessor with tremendous computational horsepower, and makes that horsepower accessible in a familiar environment – the C programming language. Scientists throughout industry and academia are already using CUDA to achieve dramatic speedups on production codes.

In this tutorial NVIDIA engineers will partner with academic and industrial researchers to present CUDA and discuss its advanced use for science and engineering domains. The morning session will introduce CUDA programming and the execution and memory models at its heart, motivate the use of CUDA with many brief examples from different HPC domains, and discuss fundamental algorithmic building blocks in CUDA. The afternoon will discuss advanced issues such as optimization and “tips & tricks”, and include real-world case studies from domain scientists using CUDA.

from what i've read so far, some very interesting parallel implementations are being developed from what would seem to be inherently serial algorithms. the parallel prefix sum in CUDA is one clever example. to illustrate, the serial algorithm looks like:
out[0] = 0
for i=1:n
   out[i] = out[i-1] + in[i-1]
parallelizing that in a work efficient and memory access friendly way is pretty cool methinks. some other useful already-GPU-implemented algorithms are separable filters, incremental gaussian computation, and random number "generation".

the extra GFLOPs should come in handy for some of our nominal processing of massive data sets, but i think i have a couple novel ideas for applying GPUs to remote sensing. some other interesting applications for GPGPU in industry:
  • virus signature matching - not medical type viruses, but computer type viruses. here they apply graphics processing hardware for network processing applications.
  • encryption/decryption - sega (why sega??) implements the advanced encryption standard (AES) on GPUs
  • financial industry - for monte carlo type simulations
  • seismic processing - solving lots of equations isn't particularly novel in this regard, but they do put out lots of pretty pictures with their stuff
anyway, it's a pretty exciting time to be involved with HPC.
Posted in: math science
September 18

the wrong stuff (eccentric squares (Kuya)) by noel

via ars, NASA is now accepting applications for astronauts!

The open positions are for astronaut candidates to train for tours of duty on the International Space Station, the largest human spacecraft ever built. It is also the site for research that will prepare NASA for future long-duration human missions to the moon and other destinations. The Constellation Program is responsible for building and operating the next-generation vehicles that will carry astronauts to the space station and the moon.

Applicants must meet physical standards and educational requirements, which include a bachelor’s degree in engineering, math or science and at least three years of experience in one of these fields. Teaching experience, including experience at the K-12 level, is considered to be qualifying experience; therefore, educators are encouraged to apply.


sweet! Posted in: math science
July 12

al gore rhythm (eccentric squares (Kuya)) by noel



when algorithms are discussed in pop culture, it's usually to drop in some complicated sounding buzzwords into scenes where the intent is to add some level of scientific credibility, or perhaps indistinguishably, technical obfuscation. for example, in the middle of the transformers movie, when they're trying to determine the origin of some signal hacking the pentagon's network, some actor drops the following gem:

we're not getting anywhere. we have to stop thinking fourier transfers and start thinking quantum mechanics.

the first level of geek in me cringes at the unrelated jargon.

...and then the inadequate geek in me starts devising elaborate scenarios where haphazard combinations of such jargon could potentially make sense (please don't tell me i'm the only one that does this...). for instance, maybe fourier transforms could be used in analyzing schrödinger wave equations, which would arise in modeling the propagation of the digital signals carrying the cryptographic ciphers? anyway, whether it be an expert's dismissal or a dilettante's ignorance, it usually never ends well for me.

that being said, i've been pleasantly surprised at the (relatively) recent non-academic coverage of swarm theory algorithms. its conceptually simple, it's embarrassingly parallel implementation (fork and join particles FTW), its general applicability, and it's elegant nature make it a great tool. it appears as if others think similarly:

a national geographic article offers a biologist's insight into the intelligence of colonies in nature and then goes on to show how this understanding is used to solve unrelated problems in widely disparate areas of engineering and computer science.

discover magazine discusses how musical improvisational algorithms are implemented with swarms. that's right, computers playing jazz.

gamasutra has an article on the use of swarm algorithms in the video game industry for artificial intelligence and physics parameter optimization.

granted, pop-science magazines like discover and national geographic aren't quite pop-culture, but it's not that bad. i'm sure some of the underlying ideas in swarm intelligences can be used in a disaster movie or some kind of crazy comic book villain in the future.
Posted in: math science
June 15

optimization through socialization (eccentric squares (Kuya)) by noel

often, i come across problems that can be considered in an optimization framework. for these problems, there may exist a solution which is not necessarily unique and maybe impossible to identify as a true global solution. usually these problems come across in trying to search for some maximum or minimum.

for a funny 10 dimensional mixed discrete/continuous nonlinear maximization problem, i'm using an interesting technique called particle swarm optimization.

Particle swarm optimization (PSO) is a stochastic, population-based computer problem-solving algorithm; it is a kind of swarm intelligence that is based on social-psychological principles and provides insights into social behavior, as well as contributing to engineering applications.

the technique gains its power from the use of multiple agents (called particles here) which effectively communicate with each other on the optimality of some criteria. for an instructive example, consider a flock of birds spread out over a cornfield. the birds are looking for the most fertile area to stop to eat. individually, each bird can see some small area beneath it and each bird remembers the best area it has encountered so far. PSO algorithms would introduce inject knowledge of the best area found by the entire flock so far into the memories of all of the birds. in this way, each of the birds will direct its future movement based on its own current direction, its own memory of the best area individually encountered so far, and the collective memory of the most fertile area encountered so far by the entire flock. the collective memory identifies the current global extremum.

more specifically, PSOs are stochastic global optimization algorithms which use heuristics based on the collective behavior of decentralized/self-organized systems in a vein similar to genetic algorithms. at their core, they rely on some element of (pseudo)randomness and rough guessing based on population dynamics. similar ideas have been utilized in pop culture applications such as the wildebeests in the movie the lion king and in the Massive battle sequences in LOTR.

at each discrete time step, the particles can be seen to be flying through an n-dimensional hyperspace, where n is the number of parameters to be optimized. for each particle, for each dimension in the search space, the particle's velocity (V) is updated as a function of it's previous direction (scaled by inertia w), a local memory of its extremum (P), and the global memory of the extremum (G). for a two dimensional (X, Y) problem, the canonical PSO algorithm can be described concisely:
for I = 1 to number of particles n do
   for J=1 to number of dimensions m do
      R1=uniform random number
      R2=uniform random number
      V[I][J]=w*V[I][J]
         +C1*R1*(P[I][J]-X[I][J])
         +C2*R2*(G[J]-X[I][J])
   X[I][J] = X[I][J]+V[I][J]
   enddo
enddo

PSO algorithms seem to be pretty powerful considering their relative ease of implementation. and interestingly, they use social ideas on decidedly non social computational problems. see the related ant colony optimization for another example of algorithms based on social systems in the natural world.

In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food (see Ant communication).

Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.

Thus, when one ant finds a good (short, in other words) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" walking around the graph representing the problem to solve.

Ant colony optimization algorithms have been used to produce near-optimal solutions to the travelling salesman problem. They have an advantage over simulated annealing and genetic algorithm approaches when the graph may change dynamically; the ant colony algorithm can be run continuously and adapt to changes in real time. This is of interest in network routing and urban transportation systems.


Posted in: math science
June 14

the schwartzian transform (eccentric squares (Kuya)) by noel

i've been tinkering around with some of the features new to the 2006/2007 versions of matlab. i'm liking the arrayfun and cellfun calls, which are reminiscent of higher order function calls in other languages. i had occasion to sort a directory by modified times, which made me want to invoke a schwartzian transform. it's not quite as terse as perl (is anything?), but i think with use of lambdas and functions like arrayfun/cellfun, matlab can be as expressive as real languages like python and perl. hopefully the JIT'ter optimizes away the temporaries.



>> get_date = @(t) datenum(t.date);
>> sorted_files = schwartzian_transform(dir, get_date);

function y = schwartzian_transform(x, f)
   g = @(t) t(:,2);
   y = x(g(sortrows([arrayfun(f, x) [1:length(x)]'])));
end
 Posted in: math science

crashing through (spoilerz!) (eccentric squares (Kuya)) by noel

my favorite novel centers around the entire world going blind. in the fictional story blindness, the affliction strikes rapidly, affecting young and old. people infected with the white sickness are rendered into invalids, fumbling around to perform their most trivial of activities and losing grip on whatever humanity they had known.

crashing through is a nonfiction account of one man's blindness. michael may's list of accomplishments reads like a superhero's rather than a blind man's:
  • rode a bicycle (fast)
  • drove a car
  • attended "normal" high school and college
  • built an 85 foot radio tower in his backyard
  • holds a speed record for downhill skiing (black diamond trails with moguls at kirkwood)
  • volunteered doing physical labor in ghana
  • former CIA employee
  • inventor
  • entrepreneur
  • husband, father
this book reads more like an inspiring get off your ass and do something self help book. after going blind at the age of 3 due to an accident at home, may goes on to live a fulfilling life. the title is due to his life's philosophy of crashing through (often with great injury to himself) any obstacles that stand before him. so it's quite a decision when a doctor informs him that a newly developed stem cell based surgery can potentially restore his vision. he opts to take the risky surgery and miraculously, his vision is restored.

and there's where things get interesting. the sense of vision forms only a basis for the human visual system. the portions of his brain dealing with visual knowledge had never fully developed, leaving him incapable of performing higher levels tasks of visual comprehension like discerning sexes, recognizing objects, and perceiving depth. with vision and knowledge being inextricably linked, he could see perfectly, but he just didn't know what he was looking at.

facial recognition and other higher level visual tasks are so innate to (most of) us that we usually fail to consider the complex mechanism by which it occurs. so it may seem surprising to hear that there are medical conditions that prevent people from recognizing faces. consider what it means to see someone happy. corners of the mouth turned slightly upwards, a subtle squinting of the eyes, there are a lot of visual features which require aggregating.

in my freshmen year, i took a seminar called brain, eye, computer. the purpose of the class was to investigate the relationship between those things. it consisted mostly of a series of discussions on papers in the areas of the HVS, AI, and neurology. our final project was: "discover a new perceptual phenomenon." haha, i don't think any of us did anything of the sort, but i think i at least had some cool ideas.

the first idea was to attempt to gain insight into the human capacity for recognition by building (at the time new) photomosaic animations. by tweaking the granularity of the tiles, the hope was that it could provide some quantifiable metric for visual recognition. but my software was buggy and my ideas not clear enough, so that never got off the ground.

my final project ended up with some long-winded intimidating title, but it basically came down a simple macromedia director video of circles moving around, specifically a series of concentric circles alternating between black and white in face color. at the beginning of the video, it basically looks like a black and white bullseye. then as time goes on, each of the circles moves to the left at a different (but proportional) speed. when viewed as motion, it gives depth cues suggesting a cone rotating in 3 dimensions.

umm, so yeah, in that class, i'm not sure i learned anything about the brain, or the HVS, but i did learn how to ramble on for pages on a random topic groping at, but never grabbing onto a conclusion.
Posted in: literature , math science
April 26

fried electronics (eccentric squares (Kuya)) by noel

364...and the weekend had started out well too.

saw 300 in theatres. with the excess violence and skinemax love scenes, it was an entertaining greek-propaganda film from antiquity.

i also discovered that a street near me, "chevy chase" leads up into the mountains north of me. it makes for a nice ride as the roads are pretty twisty. it's mostly residential, so the speeds aren't as high as the ACH, but it's an enjoyable ride up. and as for why the street is named chevy chase...i think of our state's current governor and remind myself not to ask such questions.

after seeing 300 though, i realized i lost my parking ticket. $6 fee wasn't so bad, but it was a harbringer of doom. my computer display was acting up again. it looked like things were overheating again, but this time, the power supply fan was kosher. just for the hell of it, i started reseating cards and DIMMs. apparently though, i guess i didn't insert one of the memory sticks totally as i noticed a funny burning smell.

369

the funny burning smell was accompanied by a not so funny beep from my motherboard, pleading for a merciful end to it's flaming death. ummm so yeah, i ended up frying my motherboard and RAM. i thought i could recycle most of the parts though, so i went off to that socal geek paradise, fry's electronics for a new motherboard.

370
you can see the burnt contacts

my machine is an athlon 64, but i had my eye on some of those newfangled intel conroes, so i picked up a abit AB9 pro with a 6400 core2duo. i have 2 15000 RPM SATA hard drives in a RAID 0 in my current computer, so i figured i'd at least recycle those. unfortunately, i was extremely impatient and lazy 3 years ago when i bought my alienware, so i grabbed mine before PCI express became standard on AMD motherboards. subsequently, i had to buy a new videocard, opting for a cheapy nvidia 7300 GS. sadly, my 6800 GT is sitting unused on my desk. 2GB of DDR2 800 comes along for the ride. i also figured that i'd recycle my plextor DVD burner, my soundcard, and my case.

...however the case wasn't willing to participate. while attempting to remove the old motherboard from the alienware case, i stripped one of the screws that insert into the brass? spacers. for the life of me, i couldn't get it out. i even took my drill to it to try to beat the hell out of the screw, but it wasn't to be. i was gonna try to rip the board out of the case, attempting to snap the spacer out, but it's like trying to do a a triple bypass on your dog. it's just too personal. luckily for america, comp usa is closing all its stores, so i bought a ghetto case for $35 and i just recycled my 600W PS that i had bought a couple months ago.

386upon booting up again, i suddenly realized that i can't just drag over my hard drives to a new computer as the RAID set is very specific to the controller. abit uses an intel chipset to do RAID and it's not consistent with my previous set up. so after spending that money on the new hardware, i basically found out that i lost all my data. i guess there really isn't much i lost since there is no shortage of porn on the internet all my mail is in gmail and most of my pics are on flickr.

so of course, i couldn't find my windows xp CD. in conjunction with the allure of x86-64 on the core 2 duos and the new RAM caching features of vista, i decided to pick up an OEM 64 bit vista home premium copy from fry's. at $120, it's $120 more than i've ever spent on windows, but again, i have very little patience. and of course, due to the immaturity of the drivers on 64 bit vista, my monitor didn't work right. my beautiful SGI 1600SW + multilink adapter (a piece of hardware unobtanium) came around 10 years before its time, before the rise of the LCD and the standardization of DVI. for whatever reason, i can't get it to work over the DVI connector. luckily, i managed to dig up my VGA connector so 48 hours later, i can finally switch to my native 1600x1024 resolution.

vista desktop
microsoft windows vista on my new computer's desktop

and here i thought in my post xbox360 world, i'd never spend much $ on computer hardware again...


Posted in: math science , pictures

solar bursts (eccentric squares (Kuya)) by noel

i saw this article linked on the front page of google news today. coincidentally, just yesterday, i had been shown the video below. it had been recorded by the SOHO mission. SOHO sits at the L1 lagrangian point and is tasked with observing the sun. the video below records solar activity in fall 2003. if you watch what happens near halloween you can see the effect that solar storms have on satellites.

Posted in: math science , video
April 23

the empire strikes back (eccentric squares (Kuya)) by noel

this is some pretty big news. destroying a satellite using a kinetic energy weapon is no small feat. the NY times says the satellite was a Feng Yun weather satellite. according to wiki, depending on the class, these are either in sun-synchronous, geosynchronous, or polar orbits.

since the satellite was obsolete (hence a target), it would likely be in the earlier FY-1 series. sun-synchronous orbits tend to be much much lower in altitude than geosynchronous (~40000 km) orbits, but still, you try hitting a 5 ft^3 object ~1000 km away. note that also does not directly translate into "they can take our shit down anytime they want", as they would have very precise ephemeris data on the target (it is their satellite...), whereas they'd have to search on the internet to find ephemeris data on foreign (US) assets.

in the political realm, the U.S. national space policy has this prize:
The United States considers space capabilities -- including the ground and space segments and supporting links -- vital to its national interests. Consistent with this policy, the United States will: preserve its rights, capabilities, and freedom of action n space; dissuade or deter others from either impeding those rights or developing capabilities intended to do so; take those actions necessary to protect its space capabilities; respond to interference; and deny, if necessary, adversaries the use of space capabilities hostile to U.S. national interests;

taking down foreign satellites/launch vehicles is an overt act of war, so we'd likely not see this (well we do have 2 years left...), however i'm sure the current news and stated policy will be used to direct loads and loads of $ on the fear boat towards the militarization of space.
Posted in: math science , pictures
January 10

analyze this! (eccentric squares (Kuya)) by noel

got a call from ryan. a friend of his is a chemistry phd student doing an outreach project supporting local high schools. the project intend to build and supply Scanning Tunneling Microscopes to chemistry/physics? high school students for lab instruction. apparently the project could use some software help, so that's where i come in. the project's direction, it's goals, and the technology sound cool, so i'm gonna look into it to see where i can contribute.

the image below is a sample image from an IBM (industrial strength) STM. it's an example of the type of images produced by STMs. effectively, STMs produce images like blind people read braille. a tip is moved (scanned) over an area in a regular pattern. at each point in the pattern, the surface of the object being scanned is "felt" electrically (it involves tunneling in quantum mechanics ) . i suppose that's what gives images from this type of microscope that characteristic surface look. below is IBM's description:

ring
Scientists discovered a new method for confining electrons to artificial structures at the nanometer lengthscale. Surface state electrons on Cu(111) were confined to closed structures (corrals) defined by barriers built from Fe adatoms. The barriers were assembled by individually positioning Fe adatoms using the tip of a low temperature scanning tunneling microscope (STM). A circular corral of radius 71.3 Angstrom was constructed in this way out of 48 Fe adatoms. This STM image shows the direct observation of standing-wave patterns in the local density of states of the Cu(111) surface. These spatial oscillations are quantum-mechanical interference patterns caused by scattering of the two-dimensional electron gas off the Fe adatoms and point defects.

i think on performance appraisal last year, i may have had the words "data analysis and visualization". maybe it's time to put my money where my mouth is.
Posted in: math science