MapReduce for integer factorization
September 12, 2009
As part of the work towards my final examination (DEA in Spain) I wrote a short paper on how to use MapReduce, the massive data processing framework originally developed at Google as a tool for factoring large integers. This is the abstract:
Integer factorization is a very hard computational problem. Currently no efficient algorithm for integer factorization is publicly known. However, this is an important problem on which it relies the security of many real world cryptographic systems.
I present an implementation of a fast factorization algorithm on MapReduce. MapReduce is a programming model for high performance applications developed originally at Google. The quadratic sieve algorithm is split into the different MapReduce phases and compared against a standard implementation.
The paper describes the Quadratic Sieve algorithm and how to implement it with the MapReduce framework. Also I made two implementations. First using a common mathematical tool, Maple. Second, using the open source MapReduce implementation, Hadoop. The following table shows the differences in performance between both versions, normalized.
The full article in PDF format is here: MapReduce for Integer Factorization.
The paper is also availiable at arXiv.org MapReduce for Integer Factorization at arXiv.org.
The code is published under the Apache License 2.0: MapReduce for Integer Factorization.
Bundle Adustment of scenes with moving cameras
September 6, 2009
During the first part of my Ph.D. I worked with the DAVAP research group in topics related to photogrammetry and reconstruction of 3D environments. In particular the group is interested in the creation of realistic recreations of places and buildings of historical interest.
As part of my work I developed a tool to merge 3D cloud points and photographs. It is currently used to create color cloud points from a laser scan. You can find more information here.
Currently I am working in another tool to apply bundle adjustment method to a scene with a camera in movement, in order to refine the overall reconstruction. While the normal approach would try to optimize the camera parameters for all the cameras, my approach involves refining the coeficients of a particular set of polynomials that approximate the camera trajectory and orientation.
I wrote a paper describing this approach. This is the abstract:
Bundle Adjustment is a method to refine a visual reconstruction to produce jointly optimal structure and viewing parameter estimates. Bundle Adjustment is typically used in Photogrammetry and Computer Vision as the last step of a 3D scene reconstruction.
I will expose the theoretical basis of the Bundle Adjustment method, and a basic version of the algorithm, which is commonly known. From that I will develop the particular case of a scene with moving cameras. Finally I will show a detailed example of the algorithm.
The full paper is avaliable online in PDF format: Bundle Adjustment for Scenes with moving cameras.
Finance AI
August 23, 2009
FinanceAI is an open source project with the goal of providing advanced Artificial Intelligence, Statistical and Mathematical tools for amateur and sophisticated investors. The purpose was to develop a complete algorithmic trading platform with comprehensive AI and Quantitative Finance libraries. It would also provide high performance algorithms. I started this project in early 2008, but so far it didn't get past the first version, mostly because of lack of time.
The application that I released is called Predictor. Predictor is a tool that uses financial statements, income statements, balance sheets and cashflow statements and creates powerful pattern classifiers based on that data. Then it uses the classifiers to predict financial performance.
You can see more details in the FinanceAI page.
FinanceAI is open source, and relesed under the Ms-RL license. It is currently hosted on Codeplex.