Patent ID: 8074210

Claim:
A method of producing an optimized matrix triangulation algorithm, comprising: generating, by a processor, tile functions for a matrix triangulation problem; wherein one or more of the tile functions has a triangular shape, and one or more of the tile functions has a rectangular shape; measuring cost data for the tile functions with respect to a target architecture; wherein the cost data include cost data for tile functions having a triangular shape and cost data for tile functions having a rectangular shape; processing the cost data to identify optimal compositions of tiles for rows in an iteration space of the matrix triangulation problem; wherein the processing of the cost data includes, dividing the tile functions into sets of tile functions of equal height, and for each of the sets, determining an optimal composition of tiles for every row size up to a maximum row size: processing the optimal compositions of tiles to identify optimal compositions of rows for triangles in the iteration space; wherein the processing of the optimal compositions includes determining the optimal compositions of rows using costs of the sets of tile functions; and generating a sequence of tile function invocations based on the optimal compositions of tiles and the optimal compositions of rows.