No assignee for this patent application has been made.
News editors obtained the following quote from the background information supplied by the inventors: "In sparse linear algebra, Cholesky and LDL.sup.T factorizations of symmetric matrices are of importance due to their large applicability in optimization, partial differential equations, and many other areas of scientific computing. When developing threaded versions of these factorizations, it is important to have the ability to reproduce the results of computations. When this happens, the factorizations are called deterministic. Also, solutions that do not use explicit locking mechanisms are easier to port and implement with different hardware and operating systems."
As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventor's summary information for this patent application: "In accordance with the teachings described herein, systems and methods are provided for implementing a sparse deterministic direct solver. The deterministic direct solver is configured to analyze a symmetric matrix by defining a plurality of dense blocks, identify at least one task for each of the dense blocks, and identify for each task any operations on which the task is dependent. The deterministic direct solver is further configured to store in a first data structure an entry for each of the dense blocks identifying whether a precondition must be satisfied before tasks associated with the dense blocks can be initiated, store in a second data structure a status value for each of the dense blocks and make the stored status values changeable by multiple threads, and assign a plurality of the tasks to a plurality of threads, wherein each thread is assigned a unique task, wherein each of the plurality of threads executes its assigned task when the status of the dense block corresponding to its assigned task indicates that the assigned task is ready to be performed and the precondition associated with the dense block has been satisfied if the precondition exists.
BRIEF DESCRIPTION OF THE DRAWINGS
"FIG. 1 is a block diagram of an example system for implementing sparse deterministic direct solvers such as Cholesky and LDL.sup.T without using locks.
"FIG. 2 is a flow diagram that depicts an example process that the direct solver system may implement to perform Cholesky or LDL.sup.T decomposition on a symmetric matrix A.
"FIG. 3 is a flow diagram that illustrates example steps that may be performed during the symbolic analysis phase of the Cholesky or LDL.sup.T decomposition.
"FIG. 4 is a block diagram of an example Directed Acyclic Graph ('DAG') for an example dense matrix that contains 3 blocks.
"FIG. 5 is a flow diagram that depicts example steps that may be performed during the symbolic analysis phase of the Cholesky or LDL.sup.T decomposition based on a simulated DAG.
"FIG. 6 is a flow diagram that depicts example steps used in ordering the tasks during the symbolic analysis phase.
"FIG. 7 is a flow diagram that depicts example steps that may be performed to generate a dependency list and to generate list pointers.
"FIG. 8 is a flow diagram that depicts example steps for performing numerical factorization of matrix A.
"FIG. 9 is a flow diagram that illustrates an example process wherein multiple threads are assigned unique tasks during the numerical factorization phase.
"FIG. 10 is a flow diagram that depicts example steps for a thread to perform to request a new assigned task.
"FIG. 11 is a flow diagram that depicts example steps executed by a thread to perform an assigned task.
"FIG. 12 is a block diagram that illustrates relationships between example blocks in a dense matrix and example data structures utilized by the example direct solver to order tasks in a deterministic Cholesky and LDL.sup.T direct solver.
"FIG. 13 is a flow diagram that depicts an example process wherein the numerical factorization of matrix A involves multiple threads performing update, factorization and solve tasks with respect to the various blocks.
"FIG. 14 is a flow diagram that depicts an example process, with respect to a particular block, wherein during the numerical phase, the update tasks are performed before factorize or solve tasks are performed.
"FIG. 15 is a flow diagram that depicts an example process for determining when a thread can perform a factorize task.
"FIG. 16 is a flow diagrams that depicts an example process for determining when a thread can perform a solve task on a sub-diagonal block.
"FIG. 17 is a flow diagram that depicts an example process for determining when a thread can perform an update task.
"FIG. 18 is a flow diagram that depicts example steps for performing numerical factorization of matrix A
"FIGS. 19A, 19B, and 20 depict examples of systems that may be used to implement a sparse deterministic direct solver."
For additional information on this patent application, see: Andrianov,
Keywords for this news article include: Patents, Information Technology, Information and Data Architecture.
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC
Most Popular Stories
- Obama, Ukraine Discuss Russian Incursion in Crimea
- Chinese May Have Spotted Malaysia Airlines Debris
- Social Media Causee Sleep Deprivation in Students
- First-time Jobless Claims Drop Unexpectedly
- Banks Buying Little From Minority Firms: Study
- General Electric Plans IPO of Credit Card Unit
- 'Candy Crush' Maker Files IPO
- SXSW Crash Kills 2, Injures 23
- First-time U.S. Jobless Claims Hit 3-month Low
- U.S. Business Inventories Up, Retail Sales Down