You are currently browsing the tag archive for the ‘Math’ tag.
Lipton, GLL, The ABC Conjecture And Cryptography, here.
Shinichi Mochizuki recently released a series of four papers (I,II, III, IV) totaling 512 pages that claim to contain a proof of the ABC Conjecture of number theory. I understand that he is a strong mathematician, who has a strong track record, so he may be correct. Of course such a long paper will take a serious effort by the experts to check, and given the depth and importance of the ABC Conjecture, we all wish that it is correct.
Xilinx, High Performance Computing Using FPGAs, Sep 2010, here.
The shift to multicore CPUs forces application developers to adopt a parallel programming model to exploit CPU performance. Even using the newest multicore architectures, it is unclear whether the performance growth expected by the HPC end user can be delivered, especially when running the most data- and compute- intensive applications. CPU-based systems augmented with hardware accelerators as co-processors are emerging as an alternative to CPU-only systems. This has opened up opportunities for accelerators like Graphics Processing Units (GPUs), FPGAs, and other accelerator technologies to advance HPC to previously unattainable performance levels.
I buy the argument to a degree. As the number of cores per chip grow, the easy pipelining and parallelization opportunities will diminish. The argument is stronger if there are more cores per chip. 8 cores or under per general purpose chip it’s sort of a futuristic theoretical argument. More than a few programmers can figure out how to code up a 4 to 8 stage pipeline for their application without massive automated assistance. But the FPGA opportunity does exist.
The convergence of storage and Ethernet networking is driving the adoption of 40G and 100G Ethernet in data centers. Traditionally, data is brought into the processor memory space via a PCIe network interface card. However, there is a mismatch of bandwidth between PCIe (x8, Gen3) versus the Ethernet 40G and 100G protocols; with this bandwidth mismatch, PCIe (x8, Gen3) NICs cannot support Ethernet 40G and 100G protocols. This mismatch creates the opportunity for the QPI protocol to be used in networking systems. This adoption of QPI in networking and storage is in addition to HPC.
I buy the FPGA application in the NIC space. I want my NIC to go directly to L3 pinned pages, yessir I do, 100G please.
Xilinx FPGAs double their device density from one generation to the next. Peak performance of FPGAs and processors can be estimated to show the impact of doubling the performance on FPGAs [Ref 6], [Ref 7]. This doubling of capacity directly results in increased FPGA compute capabilities.
The idea proposed here is that you want to be on the exponentially increasing density curve for the FPGAs in lieu of clock speed increases you are never going to see again. Sort of a complicated bet to make for mortals, maybe.
I like how they do the comparisons though. They say here is our Virtex-n basketball player and here is the best NBA Basketball player … and they show you crusty old Mike Bibby 2012. Then they say watch as the Virtex-n basketball player takes Mike Bibby down low in the post, and notice the Virtex-n basketball player is still growing exponentially. So you can imagine how much better he will do against Mike Bibby in the post next year. Finally they say that Mike Bibby was chosen as the best NBA player for this comparison by his father Henry, who was also a great NBA player.
FPGAs tend to consume power in tens of watts, compared to other multicores and GPUs that tend to consume power in hundreds of watts. One primary reason for lower power consumption in FPGAs is that the applications typically operate between 100–300 MHz on FPGAs compared to applications on high-performance processors executing between 2–3 GHz.
Silly making Lemonade out of Lemons argument, the minute I can have my FPGAs clocked at 3 GHz I throw away the 300MHz FPGAs, no?
Intel, An Introduction to the Intel QuickPath Interconnect, QPI, Jan 2009, here.
Xilinx Research Labs/NCSA, FPGA HPC – The road beyond processors, Jul 2007, here. Need more current references but I keep hearing the same themes in arguments for FGPA HPC, so let’s think about this for a bit:
FPGAs have an opening because you are not getting any more clocks from microprocessor fab shrinks: OK.
Power density: meh. Lots of FinQuant code can run on a handful of cores. The Low Latency HFT folks cannot really afford many L2 misses. The NSA boys are talking about supercomputers for crypto not binary protocol parsing.
Microprocessors have all functions that are hardened in silicon and you pay for them whether you use them or not and you can’t use that silicon for something else: Meh, don’t really care if I use all the silicon on my 300 USD microprocessor as long as the code is running close to optimal on the parts of the silicon useful to my application. It would be nice if I got more runtime performance for my 300USD, no doubt. This point is like Advil is bad because you don’t always need to finish the bottle after you blow out your ankle. Yeah, I understand the silicon real estate is the most expensive in the world.
Benchmarks: Black Scholes 18msec FPGA @ 110 Mhz Virtex-4 203x faster than Opeteron – 2.2 Ghz: You Cannot be Serious! 3.7 microseconds per Black Scholes evaluation was competitive performance at the turn of the century. The relative speedup slides and quotations make me nervous. Oh, Celoxica provided the data – hey Black Scholes in 36 Nanoseconds on a single core of a dual core off-the-shelf general microprocessor from 2007. So the Virtex-4 does 1M Black Scholes evaluations in 18 milliseconds flat to competitive code on a dual core general purpose off-the-shelf microprocessor in 2007.
Make it easy for the users to use this hardware and get „enough of a performance‟ increase to be useful: meh, it’s for applications that do not need to go fast, for now (2007)?
Do not try to be the fastest thing around when being as fast with less power is sufficient: meh, really do not care so much about the power thing
FPGA: Different operations map to different silicon allows massive pipelining; lots of parallelism: OK. So, why bother with the previous two points?
Eggers/ U. Washington, CHiMPS, here. Eggers is reasonable.
There have been (at least) two hindrances to the widespread adoption of FPGAs by scientific application developers: having to code in a hardware description language, such as Verilog (with its accompanying hardware-based programming model) and poor FPGA memory performance for random memory accesses. CHiMPS, our C-to-FPGA synthesis compiler, solves both problems with one memory architecture, the many-cache memory model.
Many-cache organizes the small, distributed memories on an FPGA into application-specific caches, each targeting a particular data structure or region of memory in an application and each customized for the particular memory operations that access it.
CHiMPS provides all the traditional benefits we expect from caching. To reduce cache latency, CHiMPS duplicates the caches, so that they’re physically located near the hardware logic blocks that access them. To increase memory bandwidth, CHiMPS banks the caches to match the memory parallelism in the code. To increase task-level parallelism, CHiMPS duplicates caches (and their computation blocks) through loop unrolling and tiling. Despite the lack of FPGA support for cache coherency, CHiMPS facilitates data sharing among FPGA caches and between the FPGA and its CPU through a simple flushing of cached values. And in addition, to harness the potential of the massively parallel computation offered by FPGAs, CHiMPS compiles to a spatial dataflow execution model, and then provides a mechanism to order dependent memory operations to retain C memory ordering semantics.
CHiMPS’s compiler analyses automatically generate the caches from C source. The solution allows scientific programmers to retain their familiar programming environment and memory model, and at the same time provides performance that is on average 7.8x greater and power that is one fourth that of a CPU executing the same source code. The CHiMPS work has been published in the International Symposium on Computer Architecture (ISCA, 2009), the International Conference on Field Programmable Logic and Applications (FPL, 2008), and High-Performance Reconfigurable Computing Technology and Applications (HPRCTA, 2008), where it received the Best Paper Award.
Mathblogging.org, here. Math aggregated and categorized blog of blog posts.
Gowers, The Two Cultures of Mathematics, here. Problem solving vs. Theory. Gowers starts:
In his famous Rede lecture of 1959, entitled “The Two Cultures”, C. P. Snow argued that the lack of communication between the humanities and the sciences was very harmful, and he particularly criticized those working in the humanities for their lack of understanding of science. One of the most memorable passages draws attention to a lack of symmetry which still exists, in a milder form, forty years later:
A good many times I have been present at gatherings of people who, by the standards of the traditional culture, are thought highly educated and who have with considerable gusto been expressing their incredulity at the illiteracy of scientists. Once or twice I have been provoked and have asked the company how many of them could describe the Second Law of Thermodynamics. The response was cold: it was also negative. Yet I was asking something which is about the scientific equivalent of: Have you read a work of Shakespeare’s?
I would like to argue that a similar sociological phenomenon can be observed within pure mathematics, and that this is not an entirely healthy state of affairs.
Fischer, A Bust to the King’s Gambit, here. Starts:
The King’s Gambit has lost popularity, but not sympathy. Analysts treat it with kid gloves and seem reluctant to demonstrate an outright refuatation. “The Chessplayers Manual” by Gossip and Lipschutz, published in 1874, devotes 237 pages to this gambit without arriving at a conclusion. To this day the opening has been analyzed romantically – not scientifically. Moderns seem to share the same unconscious attitude that caused the old-timers to curse stubborn Steinitz: “He took the beauty out of chess.”
To the public, the player of the King’s Gambit exhibits courage and derring-do. The gambit has been making a comeback with the younger Soviet masters, notably Spassky (who defeated Bronstein, Averbach and myself with it). His victories rarely reflected the merits of the opening since his opponents went wrong in the mid-game. It is often the case, also, as with Santasiere and Bronstein, that the King’s Gambit is played with a view to a favorable endgame. Spassky told me himself the gambit doesn’t give White much, but he plays it because neither does the Ruy Lopez nor the Giuoco Piano.
The refuatation of any gambit begins with accepting it. In my opinion the King’s Gambit is busted. It loses by force.
xkcd, here. The meaning of life.
Cowen, The American Interest, What Exported America Means, here. Cowen concludes:
It’s a well-known description in the literature of political economy that the economy of a developing country may have two quite distinct tiers: a relatively dynamic export sector and a relatively backward domestic sector, often comprised largely of agriculture and local production. That used to be true of the Japanese economy in the early postwar period, and today think of the relatively efficient automobile production in Thailand, backed by Japanese capital, and compare it to the millions of Thais who grow their own food on small-scale plots or run very small local businesses. Workers clamor for posts in the better-paid export sector, but the exporting firms can absorb only so many, so they are sorted by education, social status and connections.
In the next stage of development, a country moves beyond this picture to having virtually all of its sectors become dynamic, as we have found in most of the United States, Japan after around 1970, and Western Europe. These days, this old portrait of the two-tiered economy, originally applicable to a developing economy, may be re-emerging for the United States. We had not thought through seriously enough the possibility that the world’s most technologically advanced economy would, over time, develop persistent and indeed growing productivity differentials across sectors. It clearly has, and the social and political frictions this has caused now dominate our politics—or soon will.
One way to understand this is to note a neglected implication of Moore’s Law for computer processing speed, namely that its use in the value-added process benefits some economic sectors much more than others. In this case the static sector consists of the protected services (a big chunk of health care, education and government jobs), and the dynamic sector is heavily represented in U.S. exports, often consisting of goods and services rooted in tech, connected to tech, or made much more productive by tech innovations. Piece by piece, bit by bit, we Americans are replicating the two-tiered developing economy model, albeit from a much higher base level of wealth and productivity. We may need one day to edit the Pledge of Allegiance to read: “Two sectors, under God, with liberty and justice for all, prosperity and dynamism for some.” You heard it here first.
Thurston, On Proof and Progress in Mathematics, arXiv via Tao’s blog, here. Thurston concludes:
I can easily name regrets about my career. I have not published as much as I should. There are a number of mathematical projects in addition to the ge- ometrization theorem for Haken manifolds that I have not delivered well or at all to the mathematical public. When I concentrated more on developing the infras- tructure rather than the top-level theorems in the geometric theory of 3-manifolds, I became somewhat disengaged as the subject continued to evolve; and I have not actively or effectively promoted the field or the careers of the excellent people in it. (But some degree of disengagement seems to me an almost inevitable by-product of the mentoring of graduate students and others: in order to really turn genuine research directions over to others, it’s necessary to really let go and stop oneself from thinking about them very hard.)
On the other hand, I have been busy and productive, in many different activities. Our system does not create extra time for people like me to spend on writing and research; instead, it inundates us with many requests and opportunities for extra work, and my gut reaction has been to say ‘yes’ to many of these requests and opportunities. I have put a lot of effort into non-credit-producing activities that I value just as I value proving theorems: mathematical politics, revision of my notes into a book with a high standard of communication, exploration of computing in mathematics, mathematical education, development of new forms for communica- tion of mathematics through the Geometry Center (such as our first experiment, the “Not Knot” video), directing MSRI, etc.
I think that what I have done has not maximized my “credits”. I have been in a position not to feel a strong need to compete for more credits. Indeed, I began to feel strong challenges from other things besides proving new theorems.
I do think that my actions have done well in stimulating mathematics.
stackoverflow, here. More question answering mmorpg.
Zerohedge, Spain: The Ultimate Doomsday Presentation, Carmel Asset Management slides, here.
mathoverflow, here.
MathOverflow’s primary goal is for users to ask and answer research level math questions, the sorts of questions you come across when you’re writing or reading articles or graduate level books. Of course, individual questions don’t have to be worthy of an article, and they don’t have to be about new mathematics. A typical example is, “Can this hypothesis in that theorem be relaxed in this way?”
You answer the question, vote on the merits of the questions, and ask questions while the website logs the activity. Then you get a ranking like in a mmorpg with Tao, Gowers, and Thurston in the population. Like the concept, there should be one for applied FinQuant but I suspect the field is too proprietary and secretive. The Mathoverflow leader board reminds me of the IT Crowd when Jen exclaims delightedly “The elders of the internet know who I am?”, here.
Math Online, here. Comprehensive collection of texts and lecture notes classified by topic.
Noahpinion, Thursday Roundup, here.
Scale of the Universe, here. Cool app with new age background music. Don’t know why HFT doesn’t have a version of this app.
Farnam Street, Taleb’s reading suggestions, here.
Marketplace, ’London Whale’ taking big bets in debt market, here. Sounds like a JPM credit trader sold a bunch of CDX in size so he gets a tag. London Whale? How could that not have a happy ending? “And from that day forward everyone in The City reverently and awesomely called your grandfather “The London Whale,” goodnight sleep tight”?
A small informal effort like Pink Iguana needs to lean heavily on curation for a specific audience. How narrow is the audience? Take the entire massive EcoFin community of DeLong, Wilmott, and Mankiw then subtract most of the folks who: don’t care if a 22nm semiconductor fab is competitive in 2012, haven’t compiled their code –O3 recently, or are sort of meh to the idea that there is a RDMA transport to L3. Those folks remaining might be the Pink Iguana audience if they also like: buying credit protection from AIG stories, P=NP speculation, and IEEE754. It’s the far side of the long tail.
So why curate for such a specific audience? Despite The End of Blogging, in 2012 there are remarkable and reasonably frequent publication streams from Gowers, Lipton, and Tao. The thing that is different in the last five years is the public availability of unfiltered, authoritative, and lucid commentary on specific topics. The keys are unfiltered, authoritative, and lucid. DeLong, Mankiw, Cowen, and Krugman run similarly authoritative and lucid publication streams that are more informed by their partisan backgrounds than Gowers, Lipton, and Tao. Intel, NVIDIA, and IBM have authoritative and lucid information as well, but they also have a day job to do. If folks like Gowers, Lipton, and Tao are regularly publishing there might be more, right? You just have to go look around, and maybe you figure out how something (e.g., ETP Arbitrage, Credit Derivatives, HFT, a specific floating point computation) actually works. So, Wisty curates on Pink Iguana.
Why are these folks in the Pink Iguana Hall of Heroes (listed below the Blogroll) and why should you read the Heroes?
A Credit Trader hasn’t published since 2009, he went to do other stuff, but wow what got published there was magnificent. Read Getchen Morgenson at NYT, for example this, then read The AIG Fiasco or Bond-CDS Negative Basis or How to Lose a Billion Dollars on a Trade, it is like a teenage lucidity head rush.
Avellaneda – 2010 Quant of the Year posts regularly from his NYU faculty page and covers Research and market commentary, Stochastic Calculus, PDEs for Finance, Risk and Portfolio Management.
Bookstaber – Author of the book A Demon of Our Own Design, ran Firm Risk at Salomon back in the day, and now is Senior Policy Advisor at the SEC. See Physics Envy in Finance or Human Complexity: The Strategic game of ? and ?
DeLong – Even with the constant bitching about the press and Team Republican plus the liveblogging of World War 2, I have never seen a better EcoFin website, see DeLong and Summers: Fiscal Policy in a Depressed Economy or Econ 191: Spring 2012. DeLong’s blog really is the model for curation and commentary to a large audience.
Gowers – Rouse Ball chair, Cambridge U, Fields Medal 1998, see ICM 2010 or Finding Cantor’s proof that there are transcendental numbers, and he was piqued to comment Re: Steig Larsson, or perhaps the translator Reg Keeling in Wiles meets his match. So, Salander’s picture perfect memory, capacity to defeat armed motorcycle gangs in hand-to-hand combat, and assorted other superpowers pass without comment but she thinks she has a proof of Fermat, you gotta call a mathematician to check yourself before you wreck yourself. Gowers is on the Heroes list forever, check.
Kahan – doesn’t publish so much anymore but he is the Edgar Allen Poe of floating point computations gone wrong horror stories, and they are all here. He did IEEE 754 floating point standard and won a Turing Award. When and if he has something to say, I will probably want to listen, see How Java’s Floating-Point Hurts Everyone Everywhere and Desperately Needed Remedies for the Undebuggability of Large Floating-Point Computations in Science and Engineering.
Lipton has a gloriously unique perspective presented in Godel’s Lost Letter. He provides the descriptive narrative for algorithm complexity in a public conversation typically dominated by proofs and expositions of computational models. If algorithm complexity was professional sports, its kind of like Lipton figured out there should be color commentators broadcasting live from the game. Top posts include: Interdisciplinary Research – Challenges, The Letterman Top Ten list of why P = NP is impossible, and The Singularity Is Here In Chess; its John Madden, Dick Vitale, and Andres Cantor meet Kurt Godel, John von Neumann, and Andrey Kolmogorov in the best possible way.
Tao saved the consistency of Peano Arithmetic as described here after winning a Fields Medal in 2006, see The Black Scholes Equation and Hilbert’s Fifth Problem and related topics.
Tufte is “the guy” for the visual display of quantitative information. He has been the guy at least since the early 1980s and does not really publish the same way as Gowers, Lipton, or Tao. Tufte kind of figured out his publication flow before the internet, so you buy his books and if you want to know what he is thinking about now, you go to his course. He has stuff on line, lots of it, for example see his notebooks, or about ET. The Tufte course attendance is sort of mandatory, not sure but I think that’s in Dodd-Frank Title VII, so just do it before they find out.
ISDA and Markit offer the CDS JPM CDS code here for open source download since about 2009.
James Zucker ported the code to an iPhone and recounted the tale in My First iPhone App. You can get the App from iTunes for free its called …iCDS from iJAZ Software.
Dominic O’Kane has/had his own web based calculator based on his 2008 book Modeling Single-name and Multi-name Credit Derivatives which is in turn based on a very good Lehman research report O’Kane published with Stuart Turnbull in 2003, Valuation of Credit Default Swaps.
Hull and White 2003 on Valuation of a CDO and an nth to Default CDS Without Monte Carlo Simulation. If there is a broker dealer running a PDE solver on their Credit Derivative inventory for daily P&L, find out who the head of quantitative research is there and bow before that guy because he has achieved Steve Jobs-level marketing skills.
Matlab CDS pricer, here.
BionicTurtle has a YouTube video of how to run a CDS valuation on a spreadsheet, here. Appears to be the tip of iceberg of You Tube videos explaining Credit Derivatives
Chebfun is a collection of algorithms and an open-source software system in object-oriented MATLAB which extends familiar powerful methods of numerical computation involving numbers to continuous or piecewise-continuous functions. It also implements continuous analogues of linear algebra notions like the QR decomposition and the SVD, and solves ordinary differential equations. The mathematical basis of the system combines tools of Chebyshev expansions, fast Fourier transform, barycentric interpolation, recursive zerofinding, and automatic differentiation. The project was initiated by Nick Trefethen and Zachary Battles in 2002, and the differential equations side of Chebfun was created by Toby Driscoll of the University of Delaware beginning in 2008. see http://www2.maths.ox.ac.uk/chebfun/
1712 Taylor’s Theorem;
1965 Moore’s Law;
1972 Inside the Yield Book;
1973 Structural Models Black-Scholes, Merton;
1978 K&R The C Programming Language;
1985 Cox, Ingersoll, Ross model; IEEE 754 Floating Point Standard; Intel386 x86 Architecture;
1991 Goldberg: What Every Computer Scientist Should Know About Floating Point Arithmetic; Patriot Missile Failure;
1992 Reduced Form models -Jarrow & Turnbull; Numerical Recipes in C;
1993 Intel Pentium Architectures; Microsoft Excel v5;
1994 RiskMetrics;
1995 MS 12-factor HJM million Monte Carlo paths/second Amortizing Swaptions inventory benchmark single processor
1996 Ariane 5 failure;
1997 CreditMetrics; 3rd ed. Knuth;
1998 Gosling Extensions to Java for Numerical Computing “95% of folks out there are completely clueless about floating-point”; Wilmott – happy quant stuff on line;
2000 Hull & White model; Gupton: DefaultRisk.com;
2002 Bloomberg CDSW; Server-side Linux;
2003 Sedgewick: Algorithms in Java
2006 SPEC CPU; Hennessy & Patterson: Computer Architecture;
2007 FinMath;
2008: IEEE 754 2008; Monniaux: Floating Point Verification; MIT parsing;
