Author: Community

In 1968, Volker Strassen, a young German mathematician, announced a clever algorithm to reduce the asymptotic complexity of nÿn matrix multiplication from the order of n ³ to n ^2.81. It soon became one of the most famous scientific discoveries in the 20th century and provoked numerous studies by other mathematicians to improve upon it. Although a number of improvements have been made, Strassen’s algorithm is still optimal in his original framework, the bilinear systems of 2 ÿ 2 matrix multiplication, and people are still curious how Strassen developed his algorithm. We examined it to see if we could automatically reproduce Strassen’s discovery using a search algorithm and find other algorithms of the same quality. In total, we found 608 algorithms that have the same quality as Strassen’s, including Strassen’s original algorithm. We partitioned the algorithms into nine different groups based on the way they are constructed. This paper was made possible by the combination of genetic search and linear-algebraic techniques. To the best of our knowledge, this is the first work that automatically reproduced Strassen’s algorithm, and furthermore, discovered new algorithms with equivalent asymptotic complexity using a search algorithm.

The covariance matrix adaptation evolution strategy (CMA-ES) has been successfully used to minimize functionals on vector spaces. We generalize the concept of the CMA-ES to Riemannian manifolds and evaluate its performance in two experiments. First, we minimize synthetic functionals on the 2-D sphere. Second, we consider the reconstruction of shapes in 3-D voxel data. A novel formulation of this problem leads to the minimization of edge and region-based segmentation functionals on the Riemannian manifold of parametric 3-D medial axis representation. We compare the results to gradient-based methods on manifolds and particle swarm optimization on tangent spaces and differential evolution.

Evolutionary and developmental processes are used to evolve the configurations of 3-D structures in silico to achieve desired performances. Natural systems utilize the combination of both evolution and development processes to produce remarkable performance and diversity. However, this approach has not yet been applied extensively to the design of continuous 3-D load-supporting structures. Beginning with a single artificial cell containing information analogous to a DNA sequence, a structure is grown according to the rules encoded in the sequence. Each artificial cell in the structure contains the same sequence of growth and development rules, and each artificial cell is an element in a finite element mesh representing the structure of the mature individual. Rule sequences are evolved over many generations through selection and survival of individuals in a population. Modularity and symmetry are visible in nearly every natural and engineered structure. An understanding of the evolution and expression of symmetry and modularity is emerging from recent biological research. Initial evidence of these attributes is present in the phenotypes that are developed from the artificial evolution, although neither characteristic is imposed nor selected-for directly. The computational evolutionary development approach presented here shows promise for synthesizing novel configurations of high-performance systems. The approach may advance the system design to a new paradigm, where current design strategies have difficulty producing useful solutions.