diff options
Diffstat (limited to 'extern/libmv/third_party/ldl')
| -rw-r--r-- | extern/libmv/third_party/ldl/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | extern/libmv/third_party/ldl/Doc/ChangeLog | 39 | ||||
| -rw-r--r-- | extern/libmv/third_party/ldl/Doc/lesser.txt | 504 | ||||
| -rw-r--r-- | extern/libmv/third_party/ldl/Include/ldl.h | 104 | ||||
| -rw-r--r-- | extern/libmv/third_party/ldl/README.libmv | 10 | ||||
| -rw-r--r-- | extern/libmv/third_party/ldl/README.txt | 136 | ||||
| -rw-r--r-- | extern/libmv/third_party/ldl/Source/ldl.c | 507 |
7 files changed, 0 insertions, 1305 deletions
diff --git a/extern/libmv/third_party/ldl/CMakeLists.txt b/extern/libmv/third_party/ldl/CMakeLists.txt deleted file mode 100644 index db2d40e2612..00000000000 --- a/extern/libmv/third_party/ldl/CMakeLists.txt +++ /dev/null @@ -1,5 +0,0 @@ -include_directories(../ufconfig) -include_directories(Include) -add_library(ldl Source/ldl.c) - -LIBMV_INSTALL_THIRD_PARTY_LIB(ldl) diff --git a/extern/libmv/third_party/ldl/Doc/ChangeLog b/extern/libmv/third_party/ldl/Doc/ChangeLog deleted file mode 100644 index 48c322d3e77..00000000000 --- a/extern/libmv/third_party/ldl/Doc/ChangeLog +++ /dev/null @@ -1,39 +0,0 @@ -May 31, 2007: version 2.0.0 - - * C-callable 64-bit version added - - * ported to 64-bit MATLAB - - * subdirectories added (Source/, Include/, Lib/, Demo/, Doc/, MATLAB/) - -Dec 12, 2006: version 1.3.4 - - * minor MATLAB cleanup - -Sept 11, 2006: version 1.3.1 - - * The ldl m-file renamed to ldlsparse, to avoid name conflict with the - new MATLAB ldl function (in MATLAB 7.3). - -Apr 30, 2006: version 1.3 - - * requires AMD v2.0. ldlmain.c demo program modified, since AMD can now - handle jumbled matrices. Minor change to Makefile. - -Aug 30, 2005: - - * Makefile changed to use ../UFconfig/UFconfig.mk. License changed to - GNU LGPL. - -July 4, 2005: - - * user guide added. Since no changes to the code were made, - the version number (1.1) and code release date (Apr 22, 2005) - were left unchanged. - -Apr. 22, 2005: LDL v1.1 released. - - * No real changes were made. The code was revised so - that each routine fits on a single page in the documentation. - -Dec 31, 2003: LDL v1.0 released. diff --git a/extern/libmv/third_party/ldl/Doc/lesser.txt b/extern/libmv/third_party/ldl/Doc/lesser.txt deleted file mode 100644 index 8add30ad590..00000000000 --- a/extern/libmv/third_party/ldl/Doc/lesser.txt +++ /dev/null @@ -1,504 +0,0 @@ - GNU LESSER GENERAL PUBLIC LICENSE - Version 2.1, February 1999 - - Copyright (C) 1991, 1999 Free Software Foundation, Inc. - 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - Everyone is permitted to copy and distribute verbatim copies - of this license document, but changing it is not allowed. - -[This is the first released version of the Lesser GPL. It also counts - as the successor of the GNU Library Public License, version 2, hence - the version number 2.1.] - - Preamble - - The licenses for most software are designed to take away your -freedom to share and change it. By contrast, the GNU General Public -Licenses are intended to guarantee your freedom to share and change -free software--to make sure the software is free for all its users. - - This license, the Lesser General Public License, applies to some -specially designated software packages--typically libraries--of the -Free Software Foundation and other authors who decide to use it. You -can use it too, but we suggest you first think carefully about whether -this license or the ordinary General Public License is the better -strategy to use in any particular case, based on the explanations below. - - When we speak of free software, we are referring to freedom of use, -not price. Our General Public Licenses are designed to make sure that -you have the freedom to distribute copies of free software (and charge -for this service if you wish); that you receive source code or can get -it if you want it; that you can change the software and use pieces of -it in new free programs; and that you are informed that you can do -these things. - - To protect your rights, we need to make restrictions that forbid -distributors to deny you these rights or to ask you to surrender these -rights. These restrictions translate to certain responsibilities for -you if you distribute copies of the library or if you modify it. - - For example, if you distribute copies of the library, whether gratis -or for a fee, you must give the recipients all the rights that we gave -you. You must make sure that they, too, receive or can get the source -code. If you link other code with the library, you must provide -complete object files to the recipients, so that they can relink them -with the library after making changes to the library and recompiling -it. And you must show them these terms so they know their rights. - - We protect your rights with a two-step method: (1) we copyright the -library, and (2) we offer you this license, which gives you legal -permission to copy, distribute and/or modify the library. - - To protect each distributor, we want to make it very clear that -there is no warranty for the free library. Also, if the library is -modified by someone else and passed on, the recipients should know -that what they have is not the original version, so that the original -author's reputation will not be affected by problems that might be -introduced by others. - - Finally, software patents pose a constant threat to the existence of -any free program. We wish to make sure that a company cannot -effectively restrict the users of a free program by obtaining a -restrictive license from a patent holder. Therefore, we insist that -any patent license obtained for a version of the library must be -consistent with the full freedom of use specified in this license. - - Most GNU software, including some libraries, is covered by the -ordinary GNU General Public License. This license, the GNU Lesser -General Public License, applies to certain designated libraries, and -is quite different from the ordinary General Public License. We use -this license for certain libraries in order to permit linking those -libraries into non-free programs. - - When a program is linked with a library, whether statically or using -a shared library, the combination of the two is legally speaking a -combined work, a derivative of the original library. The ordinary -General Public License therefore permits such linking only if the -entire combination fits its criteria of freedom. The Lesser General -Public License permits more lax criteria for linking other code with -the library. - - We call this license the "Lesser" General Public License because it -does Less to protect the user's freedom than the ordinary General -Public License. It also provides other free software developers Less -of an advantage over competing non-free programs. These disadvantages -are the reason we use the ordinary General Public License for many -libraries. However, the Lesser license provides advantages in certain -special circumstances. - - For example, on rare occasions, there may be a special need to -encourage the widest possible use of a certain library, so that it becomes -a de-facto standard. To achieve this, non-free programs must be -allowed to use the library. A more frequent case is that a free -library does the same job as widely used non-free libraries. In this -case, there is little to gain by limiting the free library to free -software only, so we use the Lesser General Public License. - - In other cases, permission to use a particular library in non-free -programs enables a greater number of people to use a large body of -free software. For example, permission to use the GNU C Library in -non-free programs enables many more people to use the whole GNU -operating system, as well as its variant, the GNU/Linux operating -system. - - Although the Lesser General Public License is Less protective of the -users' freedom, it does ensure that the user of a program that is -linked with the Library has the freedom and the wherewithal to run -that program using a modified version of the Library. - - The precise terms and conditions for copying, distribution and -modification follow. Pay close attention to the difference between a -"work based on the library" and a "work that uses the library". The -former contains code derived from the library, whereas the latter must -be combined with the library in order to run. - - GNU LESSER GENERAL PUBLIC LICENSE - TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION - - 0. This License Agreement applies to any software library or other -program which contains a notice placed by the copyright holder or -other authorized party saying it may be distributed under the terms of -this Lesser General Public License (also called "this License"). -Each licensee is addressed as "you". - - A "library" means a collection of software functions and/or data -prepared so as to be conveniently linked with application programs -(which use some of those functions and data) to form executables. - - The "Library", below, refers to any such software library or work -which has been distributed under these terms. A "work based on the -Library" means either the Library or any derivative work under -copyright law: that is to say, a work containing the Library or a -portion of it, either verbatim or with modifications and/or translated -straightforwardly into another language. (Hereinafter, translation is -included without limitation in the term "modification".) - - "Source code" for a work means the preferred form of the work for -making modifications to it. For a library, complete source code means -all the source code for all modules it contains, plus any associated -interface definition files, plus the scripts used to control compilation -and installation of the library. - - Activities other than copying, distribution and modification are not -covered by this License; they are outside its scope. The act of -running a program using the Library is not restricted, and output from -such a program is covered only if its contents constitute a work based -on the Library (independent of the use of the Library in a tool for -writing it). Whether that is true depends on what the Library does -and what the program that uses the Library does. - - 1. You may copy and distribute verbatim copies of the Library's -complete source code as you receive it, in any medium, provided that -you conspicuously and appropriately publish on each copy an -appropriate copyright notice and disclaimer of warranty; keep intact -all the notices that refer to this License and to the absence of any -warranty; and distribute a copy of this License along with the -Library. - - You may charge a fee for the physical act of transferring a copy, -and you may at your option offer warranty protection in exchange for a -fee. - - 2. You may modify your copy or copies of the Library or any portion -of it, thus forming a work based on the Library, and copy and -distribute such modifications or work under the terms of Section 1 -above, provided that you also meet all of these conditions: - - a) The modified work must itself be a software library. - - b) You must cause the files modified to carry prominent notices - stating that you changed the files and the date of any change. - - c) You must cause the whole of the work to be licensed at no - charge to all third parties under the terms of this License. - - d) If a facility in the modified Library refers to a function or a - table of data to be supplied by an application program that uses - the facility, other than as an argument passed when the facility - is invoked, then you must make a good faith effort to ensure that, - in the event an application does not supply such function or - table, the facility still operates, and performs whatever part of - its purpose remains meaningful. - - (For example, a function in a library to compute square roots has - a purpose that is entirely well-defined independent of the - application. Therefore, Subsection 2d requires that any - application-supplied function or table used by this function must - be optional: if the application does not supply it, the square - root function must still compute square roots.) - -These requirements apply to the modified work as a whole. If -identifiable sections of that work are not derived from the Library, -and can be reasonably considered independent and separate works in -themselves, then this License, and its terms, do not apply to those -sections when you distribute them as separate works. But when you -distribute the same sections as part of a whole which is a work based -on the Library, the distribution of the whole must be on the terms of -this License, whose permissions for other licensees extend to the -entire whole, and thus to each and every part regardless of who wrote -it. - -Thus, it is not the intent of this section to claim rights or contest -your rights to work written entirely by you; rather, the intent is to -exercise the right to control the distribution of derivative or -collective works based on the Library. - -In addition, mere aggregation of another work not based on the Library -with the Library (or with a work based on the Library) on a volume of -a storage or distribution medium does not bring the other work under -the scope of this License. - - 3. You may opt to apply the terms of the ordinary GNU General Public -License instead of this License to a given copy of the Library. To do -this, you must alter all the notices that refer to this License, so -that they refer to the ordinary GNU General Public License, version 2, -instead of to this License. (If a newer version than version 2 of the -ordinary GNU General Public License has appeared, then you can specify -that version instead if you wish.) Do not make any other change in -these notices. - - Once this change is made in a given copy, it is irreversible for -that copy, so the ordinary GNU General Public License applies to all -subsequent copies and derivative works made from that copy. - - This option is useful when you wish to copy part of the code of -the Library into a program that is not a library. - - 4. You may copy and distribute the Library (or a portion or -derivative of it, under Section 2) in object code or executable form -under the terms of Sections 1 and 2 above provided that you accompany -it with the complete corresponding machine-readable source code, which -must be distributed under the terms of Sections 1 and 2 above on a -medium customarily used for software interchange. - - If distribution of object code is made by offering access to copy -from a designated place, then offering equivalent access to copy the -source code from the same place satisfies the requirement to -distribute the source code, even though third parties are not -compelled to copy the source along with the object code. - - 5. A program that contains no derivative of any portion of the -Library, but is designed to work with the Library by being compiled or -linked with it, is called a "work that uses the Library". Such a -work, in isolation, is not a derivative work of the Library, and -therefore falls outside the scope of this License. - - However, linking a "work that uses the Library" with the Library -creates an executable that is a derivative of the Library (because it -contains portions of the Library), rather than a "work that uses the -library". The executable is therefore covered by this License. -Section 6 states terms for distribution of such executables. - - When a "work that uses the Library" uses material from a header file -that is part of the Library, the object code for the work may be a -derivative work of the Library even though the source code is not. -Whether this is true is especially significant if the work can be -linked without the Library, or if the work is itself a library. The -threshold for this to be true is not precisely defined by law. - - If such an object file uses only numerical parameters, data -structure layouts and accessors, and small macros and small inline -functions (ten lines or less in length), then the use of the object -file is unrestricted, regardless of whether it is legally a derivative -work. (Executables containing this object code plus portions of the -Library will still fall under Section 6.) - - Otherwise, if the work is a derivative of the Library, you may -distribute the object code for the work under the terms of Section 6. -Any executables containing that work also fall under Section 6, -whether or not they are linked directly with the Library itself. - - 6. As an exception to the Sections above, you may also combine or -link a "work that uses the Library" with the Library to produce a -work containing portions of the Library, and distribute that work -under terms of your choice, provided that the terms permit -modification of the work for the customer's own use and reverse -engineering for debugging such modifications. - - You must give prominent notice with each copy of the work that the -Library is used in it and that the Library and its use are covered by -this License. You must supply a copy of this License. If the work -during execution displays copyright notices, you must include the -copyright notice for the Library among them, as well as a reference -directing the user to the copy of this License. Also, you must do one -of these things: - - a) Accompany the work with the complete corresponding - machine-readable source code for the Library including whatever - changes were used in the work (which must be distributed under - Sections 1 and 2 above); and, if the work is an executable linked - with the Library, with the complete machine-readable "work that - uses the Library", as object code and/or source code, so that the - user can modify the Library and then relink to produce a modified - executable containing the modified Library. (It is understood - that the user who changes the contents of definitions files in the - Library will not necessarily be able to recompile the application - to use the modified definitions.) - - b) Use a suitable shared library mechanism for linking with the - Library. A suitable mechanism is one that (1) uses at run time a - copy of the library already present on the user's computer system, - rather than copying library functions into the executable, and (2) - will operate properly with a modified version of the library, if - the user installs one, as long as the modified version is - interface-compatible with the version that the work was made with. - - c) Accompany the work with a written offer, valid for at - least three years, to give the same user the materials - specified in Subsection 6a, above, for a charge no more - than the cost of performing this distribution. - - d) If distribution of the work is made by offering access to copy - from a designated place, offer equivalent access to copy the above - specified materials from the same place. - - e) Verify that the user has already received a copy of these - materials or that you have already sent this user a copy. - - For an executable, the required form of the "work that uses the -Library" must include any data and utility programs needed for -reproducing the executable from it. However, as a special exception, -the materials to be distributed need not include anything that is -normally distributed (in either source or binary form) with the major -components (compiler, kernel, and so on) of the operating system on -which the executable runs, unless that component itself accompanies -the executable. - - It may happen that this requirement contradicts the license -restrictions of other proprietary libraries that do not normally -accompany the operating system. Such a contradiction means you cannot -use both them and the Library together in an executable that you -distribute. - - 7. You may place library facilities that are a work based on the -Library side-by-side in a single library together with other library -facilities not covered by this License, and distribute such a combined -library, provided that the separate distribution of the work based on -the Library and of the other library facilities is otherwise -permitted, and provided that you do these two things: - - a) Accompany the combined library with a copy of the same work - based on the Library, uncombined with any other library - facilities. This must be distributed under the terms of the - Sections above. - - b) Give prominent notice with the combined library of the fact - that part of it is a work based on the Library, and explaining - where to find the accompanying uncombined form of the same work. - - 8. You may not copy, modify, sublicense, link with, or distribute -the Library except as expressly provided under this License. Any -attempt otherwise to copy, modify, sublicense, link with, or -distribute the Library is void, and will automatically terminate your -rights under this License. However, parties who have received copies, -or rights, from you under this License will not have their licenses -terminated so long as such parties remain in full compliance. - - 9. You are not required to accept this License, since you have not -signed it. However, nothing else grants you permission to modify or -distribute the Library or its derivative works. These actions are -prohibited by law if you do not accept this License. Therefore, by -modifying or distributing the Library (or any work based on the -Library), you indicate your acceptance of this License to do so, and -all its terms and conditions for copying, distributing or modifying -the Library or works based on it. - - 10. Each time you redistribute the Library (or any work based on the -Library), the recipient automatically receives a license from the -original licensor to copy, distribute, link with or modify the Library -subject to these terms and conditions. You may not impose any further -restrictions on the recipients' exercise of the rights granted herein. -You are not responsible for enforcing compliance by third parties with -this License. - - 11. If, as a consequence of a court judgment or allegation of patent -infringement or for any other reason (not limited to patent issues), -conditions are imposed on you (whether by court order, agreement or -otherwise) that contradict the conditions of this License, they do not -excuse you from the conditions of this License. If you cannot -distribute so as to satisfy simultaneously your obligations under this -License and any other pertinent obligations, then as a consequence you -may not distribute the Library at all. For example, if a patent -license would not permit royalty-free redistribution of the Library by -all those who receive copies directly or indirectly through you, then -the only way you could satisfy both it and this License would be to -refrain entirely from distribution of the Library. - -If any portion of this section is held invalid or unenforceable under any -particular circumstance, the balance of the section is intended to apply, -and the section as a whole is intended to apply in other circumstances. - -It is not the purpose of this section to induce you to infringe any -patents or other property right claims or to contest validity of any -such claims; this section has the sole purpose of protecting the -integrity of the free software distribution system which is -implemented by public license practices. Many people have made -generous contributions to the wide range of software distributed -through that system in reliance on consistent application of that -system; it is up to the author/donor to decide if he or she is willing -to distribute software through any other system and a licensee cannot -impose that choice. - -This section is intended to make thoroughly clear what is believed to -be a consequence of the rest of this License. - - 12. If the distribution and/or use of the Library is restricted in -certain countries either by patents or by copyrighted interfaces, the -original copyright holder who places the Library under this License may add -an explicit geographical distribution limitation excluding those countries, -so that distribution is permitted only in or among countries not thus -excluded. In such case, this License incorporates the limitation as if -written in the body of this License. - - 13. The Free Software Foundation may publish revised and/or new -versions of the Lesser General Public License from time to time. -Such new versions will be similar in spirit to the present version, -but may differ in detail to address new problems or concerns. - -Each version is given a distinguishing version number. If the Library -specifies a version number of this License which applies to it and -"any later version", you have the option of following the terms and -conditions either of that version or of any later version published by -the Free Software Foundation. If the Library does not specify a -license version number, you may choose any version ever published by -the Free Software Foundation. - - 14. If you wish to incorporate parts of the Library into other free -programs whose distribution conditions are incompatible with these, -write to the author to ask for permission. For software which is -copyrighted by the Free Software Foundation, write to the Free -Software Foundation; we sometimes make exceptions for this. Our -decision will be guided by the two goals of preserving the free status -of all derivatives of our free software and of promoting the sharing -and reuse of software generally. - - NO WARRANTY - - 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO -WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. -EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR -OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY -KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE -IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR -PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE -LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME -THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. - - 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN -WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY -AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU -FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR -CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE -LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING -RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A -FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF -SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH -DAMAGES. - - END OF TERMS AND CONDITIONS - - How to Apply These Terms to Your New Libraries - - If you develop a new library, and you want it to be of the greatest -possible use to the public, we recommend making it free software that -everyone can redistribute and change. You can do so by permitting -redistribution under these terms (or, alternatively, under the terms of the -ordinary General Public License). - - To apply these terms, attach the following notices to the library. It is -safest to attach them to the start of each source file to most effectively -convey the exclusion of warranty; and each file should have at least the -"copyright" line and a pointer to where the full notice is found. - - <one line to give the library's name and a brief idea of what it does.> - Copyright (C) <year> <name of author> - - This library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. - - This library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with this library; if not, write to the Free Software - Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - -Also add information on how to contact you by electronic and paper mail. - -You should also get your employer (if you work as a programmer) or your -school, if any, to sign a "copyright disclaimer" for the library, if -necessary. Here is a sample; alter the names: - - Yoyodyne, Inc., hereby disclaims all copyright interest in the - library `Frob' (a library for tweaking knobs) written by James Random Hacker. - - <signature of Ty Coon>, 1 April 1990 - Ty Coon, President of Vice - -That's all there is to it! - - diff --git a/extern/libmv/third_party/ldl/Include/ldl.h b/extern/libmv/third_party/ldl/Include/ldl.h deleted file mode 100644 index 5840be322f7..00000000000 --- a/extern/libmv/third_party/ldl/Include/ldl.h +++ /dev/null @@ -1,104 +0,0 @@ -/* ========================================================================== */ -/* === ldl.h: include file for the LDL package ============================= */ -/* ========================================================================== */ - -/* LDL Copyright (c) Timothy A Davis, - * University of Florida. All Rights Reserved. See README for the License. - */ - -#include "UFconfig.h" - -#ifdef LDL_LONG -#define LDL_int UF_long -#define LDL_ID UF_long_id - -#define LDL_symbolic ldl_l_symbolic -#define LDL_numeric ldl_l_numeric -#define LDL_lsolve ldl_l_lsolve -#define LDL_dsolve ldl_l_dsolve -#define LDL_ltsolve ldl_l_ltsolve -#define LDL_perm ldl_l_perm -#define LDL_permt ldl_l_permt -#define LDL_valid_perm ldl_l_valid_perm -#define LDL_valid_matrix ldl_l_valid_matrix - -#else -#define LDL_int int -#define LDL_ID "%d" - -#define LDL_symbolic ldl_symbolic -#define LDL_numeric ldl_numeric -#define LDL_lsolve ldl_lsolve -#define LDL_dsolve ldl_dsolve -#define LDL_ltsolve ldl_ltsolve -#define LDL_perm ldl_perm -#define LDL_permt ldl_permt -#define LDL_valid_perm ldl_valid_perm -#define LDL_valid_matrix ldl_valid_matrix - -#endif - -/* ========================================================================== */ -/* === int version ========================================================== */ -/* ========================================================================== */ - -void ldl_symbolic (int n, int Ap [ ], int Ai [ ], int Lp [ ], - int Parent [ ], int Lnz [ ], int Flag [ ], int P [ ], int Pinv [ ]) ; - -int ldl_numeric (int n, int Ap [ ], int Ai [ ], double Ax [ ], - int Lp [ ], int Parent [ ], int Lnz [ ], int Li [ ], double Lx [ ], - double D [ ], double Y [ ], int Pattern [ ], int Flag [ ], - int P [ ], int Pinv [ ]) ; - -void ldl_lsolve (int n, double X [ ], int Lp [ ], int Li [ ], - double Lx [ ]) ; - -void ldl_dsolve (int n, double X [ ], double D [ ]) ; - -void ldl_ltsolve (int n, double X [ ], int Lp [ ], int Li [ ], - double Lx [ ]) ; - -void ldl_perm (int n, double X [ ], double B [ ], int P [ ]) ; -void ldl_permt (int n, double X [ ], double B [ ], int P [ ]) ; - -int ldl_valid_perm (int n, int P [ ], int Flag [ ]) ; -int ldl_valid_matrix ( int n, int Ap [ ], int Ai [ ]) ; - -/* ========================================================================== */ -/* === long version ========================================================= */ -/* ========================================================================== */ - -void ldl_l_symbolic (UF_long n, UF_long Ap [ ], UF_long Ai [ ], UF_long Lp [ ], - UF_long Parent [ ], UF_long Lnz [ ], UF_long Flag [ ], UF_long P [ ], - UF_long Pinv [ ]) ; - -UF_long ldl_l_numeric (UF_long n, UF_long Ap [ ], UF_long Ai [ ], double Ax [ ], - UF_long Lp [ ], UF_long Parent [ ], UF_long Lnz [ ], UF_long Li [ ], - double Lx [ ], double D [ ], double Y [ ], UF_long Pattern [ ], - UF_long Flag [ ], UF_long P [ ], UF_long Pinv [ ]) ; - -void ldl_l_lsolve (UF_long n, double X [ ], UF_long Lp [ ], UF_long Li [ ], - double Lx [ ]) ; - -void ldl_l_dsolve (UF_long n, double X [ ], double D [ ]) ; - -void ldl_l_ltsolve (UF_long n, double X [ ], UF_long Lp [ ], UF_long Li [ ], - double Lx [ ]) ; - -void ldl_l_perm (UF_long n, double X [ ], double B [ ], UF_long P [ ]) ; -void ldl_l_permt (UF_long n, double X [ ], double B [ ], UF_long P [ ]) ; - -UF_long ldl_l_valid_perm (UF_long n, UF_long P [ ], UF_long Flag [ ]) ; -UF_long ldl_l_valid_matrix ( UF_long n, UF_long Ap [ ], UF_long Ai [ ]) ; - -/* ========================================================================== */ -/* === LDL version ========================================================== */ -/* ========================================================================== */ - -#define LDL_DATE "Nov 1, 2007" -#define LDL_VERSION_CODE(main,sub) ((main) * 1000 + (sub)) -#define LDL_MAIN_VERSION 2 -#define LDL_SUB_VERSION 0 -#define LDL_SUBSUB_VERSION 1 -#define LDL_VERSION LDL_VERSION_CODE(LDL_MAIN_VERSION,LDL_SUB_VERSION) - diff --git a/extern/libmv/third_party/ldl/README.libmv b/extern/libmv/third_party/ldl/README.libmv deleted file mode 100644 index 64ece48a390..00000000000 --- a/extern/libmv/third_party/ldl/README.libmv +++ /dev/null @@ -1,10 +0,0 @@ -Project: LDL -URL: http://www.cise.ufl.edu/research/sparse/ldl/ -License: LGPL2.1 -Upstream version: 2.0.1 (despite the ChangeLog saying 2.0.0) - -Local modifications: - - * Deleted everything except ldl.c, ldl.h, the license, the ChangeLog, and the - README. - diff --git a/extern/libmv/third_party/ldl/README.txt b/extern/libmv/third_party/ldl/README.txt deleted file mode 100644 index 7be8dd1f001..00000000000 --- a/extern/libmv/third_party/ldl/README.txt +++ /dev/null @@ -1,136 +0,0 @@ -LDL Version 2.0: a sparse LDL' factorization and solve package. - Written in C, with both a C and MATLAB mexFunction interface. - -These routines are not terrifically fast (they do not use dense matrix kernels), -but the code is very short and concise. The purpose is to illustrate the -algorithms in a very concise and readable manner, primarily for educational -purposes. Although the code is very concise, this package is slightly faster -than the built-in sparse Cholesky factorization in MATLAB 6.5 (chol), when -using the same input permutation. - -Requires UFconfig, in the ../UFconfig directory relative to this directory. - -Quick start (Unix, or Windows with Cygwin): - - To compile, test, and install LDL, you may wish to first obtain a copy of - AMD v2.0 from http://www.cise.ufl.edu/research/sparse, and place it in the - ../AMD directory, relative to this directory. Next, type "make", which - will compile the LDL library and three demo main programs (one of which - requires AMD). It will also compile the LDL MATLAB mexFunction (if you - have MATLAB). Typing "make clean" will remove non-essential files. - AMD v2.0 or later is required. Its use is optional. - -Quick start (for MATLAB users); - - To compile, test, and install the LDL mexFunctions (ldlsparse and - ldlsymbol), start MATLAB in this directory and type ldl_install. - This works on any system supported by MATLAB. - --------------------------------------------------------------------------------- - -LDL Copyright (c) 2005 by Timothy A. Davis. All Rights Reserved. - -LDL License: - - Your use or distribution of LDL or any modified version of - LDL implies that you agree to this License. - - This library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. - - This library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with this library; if not, write to the Free Software - Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 - USA - - Permission is hereby granted to use or copy this program under the - terms of the GNU LGPL, provided that the Copyright, this License, - and the Availability of the original version is retained on all copies. - User documentation of any code that uses this code or any modified - version of this code must cite the Copyright, this License, the - Availability note, and "Used by permission." Permission to modify - the code and to distribute modified code is granted, provided the - Copyright, this License, and the Availability note are retained, - and a notice that the code was modified is included. - -Availability: - - http://www.cise.ufl.edu/research/sparse/ldl - -Acknowledgements: - - This work was supported by the National Science Foundation, under - grant CCR-0203270. - - Portions of this work were done while on sabbatical at Stanford University - and Lawrence Berkeley National Laboratory (with funding from the SciDAC - program). I would like to thank Gene Golub, Esmond Ng, and Horst Simon - for making this sabbatical possible. I would like to thank Pete Stewart - for his comments on a draft of this software and paper. - --------------------------------------------------------------------------------- -Files and directories in this distribution: --------------------------------------------------------------------------------- - - Documentation, and compiling: - - README.txt this file - Makefile for compiling LDL - ChangeLog changes since V1.0 (Dec 31, 2003) - License license - lesser.txt the GNU LGPL license - - ldl_userguide.pdf user guide in PDF - ldl_userguide.ps user guide in postscript - ldl_userguide.tex user guide in Latex - ldl.bib bibliography for user guide - - The LDL library itself: - - ldl.c the C-callable routines - ldl.h include file for any code that calls LDL - - A simple C main program that demonstrates how to use LDL: - - ldlsimple.c a stand-alone C program, uses the basic features of LDL - ldlsimple.out output of ldlsimple - - ldllsimple.c long integer version of ldlsimple.c - - Demo C program, for testing LDL and providing an example of its use - - ldlmain.c a stand-alone C main program that uses and tests LDL - Matrix a directory containing matrices used by ldlmain.c - ldlmain.out output of ldlmain - ldlamd.out output of ldlamd (ldlmain.c compiled with AMD) - ldllamd.out output of ldllamd (ldlmain.c compiled with AMD, long) - - MATLAB-related, not required for use in a regular C program - - Contents.m a list of the MATLAB-callable routines - ldl.m MATLAB help file for the LDL mexFunction - ldldemo.m MATLAB demo of how to use the LDL mexFunction - ldldemo.out diary output of ldldemo - ldltest.m to test the LDL mexFunction - ldltest.out diary output of ldltest - ldlmex.c the LDL mexFunction for MATLAB - ldlrow.m the numerical algorithm that LDL is based on - ldlmain2.m compiles and runs ldlmain.c as a MATLAB mexFunction - ldlmain2.out output of ldlmain2.m - ldlsymbolmex.c symbolic factorization using LDL (see SYMBFACT, ETREE) - ldlsymbol.m help file for the LDLSYMBOL mexFunction - - ldl_install.m compile, install, and test LDL functions - ldl_make.m compile LDL (ldlsparse and ldlsymbol) - - ldlsparse.m help for ldlsparse - -See ldl.c for a description of how to use the code from a C program. Type -"help ldl" in MATLAB for information on how to use LDL in a MATLAB program. diff --git a/extern/libmv/third_party/ldl/Source/ldl.c b/extern/libmv/third_party/ldl/Source/ldl.c deleted file mode 100644 index a9b35c846ef..00000000000 --- a/extern/libmv/third_party/ldl/Source/ldl.c +++ /dev/null @@ -1,507 +0,0 @@ -/* ========================================================================== */ -/* === ldl.c: sparse LDL' factorization and solve package =================== */ -/* ========================================================================== */ - -/* LDL: a simple set of routines for sparse LDL' factorization. These routines - * are not terrifically fast (they do not use dense matrix kernels), but the - * code is very short. The purpose is to illustrate the algorithms in a very - * concise manner, primarily for educational purposes. Although the code is - * very concise, this package is slightly faster than the built-in sparse - * Cholesky factorization in MATLAB 7.0 (chol), when using the same input - * permutation. - * - * The routines compute the LDL' factorization of a real sparse symmetric - * matrix A (or PAP' if a permutation P is supplied), and solve upper - * and lower triangular systems with the resulting L and D factors. If A is - * positive definite then the factorization will be accurate. A can be - * indefinite (with negative values on the diagonal D), but in this case no - * guarantee of accuracy is provided, since no numeric pivoting is performed. - * - * The n-by-n sparse matrix A is in compressed-column form. The nonzero values - * in column j are stored in Ax [Ap [j] ... Ap [j+1]-1], with corresponding row - * indices in Ai [Ap [j] ... Ap [j+1]-1]. Ap [0] = 0 is required, and thus - * nz = Ap [n] is the number of nonzeros in A. Ap is an int array of size n+1. - * The int array Ai and the double array Ax are of size nz. This data structure - * is identical to the one used by MATLAB, except for the following - * generalizations. The row indices in each column of A need not be in any - * particular order, although they must be in the range 0 to n-1. Duplicate - * entries can be present; any duplicates are summed. That is, if row index i - * appears twice in a column j, then the value of A (i,j) is the sum of the two - * entries. The data structure used here for the input matrix A is more - * flexible than MATLAB's, which requires sorted columns with no duplicate - * entries. - * - * Only the diagonal and upper triangular part of A (or PAP' if a permutation - * P is provided) is accessed. The lower triangular parts of the matrix A or - * PAP' can be present, but they are ignored. - * - * The optional input permutation is provided as an array P of length n. If - * P [k] = j, the row and column j of A is the kth row and column of PAP'. - * If P is present then the factorization is LDL' = PAP' or L*D*L' = A(P,P) in - * 0-based MATLAB notation. If P is not present (a null pointer) then no - * permutation is performed, and the factorization is LDL' = A. - * - * The lower triangular matrix L is stored in the same compressed-column - * form (an int Lp array of size n+1, an int Li array of size Lp [n], and a - * double array Lx of the same size as Li). It has a unit diagonal, which is - * not stored. The row indices in each column of L are always returned in - * ascending order, with no duplicate entries. This format is compatible with - * MATLAB, except that it would be more convenient for MATLAB to include the - * unit diagonal of L. Doing so here would add additional complexity to the - * code, and is thus omitted in the interest of keeping this code short and - * readable. - * - * The elimination tree is held in the Parent [0..n-1] array. It is normally - * not required by the user, but it is required by ldl_numeric. The diagonal - * matrix D is held as an array D [0..n-1] of size n. - * - * -------------------- - * C-callable routines: - * -------------------- - * - * ldl_symbolic: Given the pattern of A, computes the Lp and Parent arrays - * required by ldl_numeric. Takes time proportional to the number of - * nonzeros in L. Computes the inverse Pinv of P if P is provided. - * Also returns Lnz, the count of nonzeros in each column of L below - * the diagonal (this is not required by ldl_numeric). - * ldl_numeric: Given the pattern and numerical values of A, the Lp array, - * the Parent array, and P and Pinv if applicable, computes the - * pattern and numerical values of L and D. - * ldl_lsolve: Solves Lx=b for a dense vector b. - * ldl_dsolve: Solves Dx=b for a dense vector b. - * ldl_ltsolve: Solves L'x=b for a dense vector b. - * ldl_perm: Computes x=Pb for a dense vector b. - * ldl_permt: Computes x=P'b for a dense vector b. - * ldl_valid_perm: checks the validity of a permutation vector - * ldl_valid_matrix: checks the validity of the sparse matrix A - * - * ---------------------------- - * Limitations of this package: - * ---------------------------- - * - * In the interest of keeping this code simple and readable, ldl_symbolic and - * ldl_numeric assume their inputs are valid. You can check your own inputs - * prior to calling these routines with the ldl_valid_perm and ldl_valid_matrix - * routines. Except for the two ldl_valid_* routines, no routine checks to see - * if the array arguments are present (non-NULL). Like all C routines, no - * routine can determine if the arrays are long enough and don't overlap. - * - * The ldl_numeric does check the numerical factorization, however. It returns - * n if the factorization is successful. If D (k,k) is zero, then k is - * returned, and L is only partially computed. - * - * No pivoting to control fill-in is performed, which is often critical for - * obtaining good performance. I recommend that you compute the permutation P - * using AMD or SYMAMD (approximate minimum degree ordering routines), or an - * appropriate graph-partitioning based ordering. See the ldldemo.m routine for - * an example in MATLAB, and the ldlmain.c stand-alone C program for examples of - * how to find P. Routines for manipulating compressed-column matrices are - * available in UMFPACK. AMD, SYMAMD, UMFPACK, and this LDL package are all - * available at http://www.cise.ufl.edu/research/sparse. - * - * ------------------------- - * Possible simplifications: - * ------------------------- - * - * These routines could be made even simpler with a few additional assumptions. - * If no input permutation were performed, the caller would have to permute the - * matrix first, but the computation of Pinv, and the use of P and Pinv could be - * removed. If only the diagonal and upper triangular part of A or PAP' are - * present, then the tests in the "if (i < k)" statement in ldl_symbolic and - * "if (i <= k)" in ldl_numeric, are always true, and could be removed (i can - * equal k in ldl_symbolic, but then the body of the if statement would - * correctly do no work since Flag [k] == k). If we could assume that no - * duplicate entries are present, then the statement Y [i] += Ax [p] could be - * replaced with Y [i] = Ax [p] in ldl_numeric. - * - * -------------------------- - * Description of the method: - * -------------------------- - * - * LDL computes the symbolic factorization by finding the pattern of L one row - * at a time. It does this based on the following theory. Consider a sparse - * system Lx=b, where L, x, and b, are all sparse, and where L comes from a - * Cholesky (or LDL') factorization. The elimination tree (etree) of L is - * defined as follows. The parent of node j is the smallest k > j such that - * L (k,j) is nonzero. Node j has no parent if column j of L is completely zero - * below the diagonal (j is a root of the etree in this case). The nonzero - * pattern of x is the union of the paths from each node i to the root, for - * each nonzero b (i). To compute the numerical solution to Lx=b, we can - * traverse the columns of L corresponding to nonzero values of x. This - * traversal does not need to be done in the order 0 to n-1. It can be done in - * any "topological" order, such that x (i) is computed before x (j) if i is a - * descendant of j in the elimination tree. - * - * The row-form of the LDL' factorization is shown in the MATLAB function - * ldlrow.m in this LDL package. Note that row k of L is found via a sparse - * triangular solve of L (1:k-1, 1:k-1) \ A (1:k-1, k), to use 1-based MATLAB - * notation. Thus, we can start with the nonzero pattern of the kth column of - * A (above the diagonal), follow the paths up to the root of the etree of the - * (k-1)-by-(k-1) leading submatrix of L, and obtain the pattern of the kth row - * of L. Note that we only need the leading (k-1)-by-(k-1) submatrix of L to - * do this. The elimination tree can be constructed as we go. - * - * The symbolic factorization does the same thing, except that it discards the - * pattern of L as it is computed. It simply counts the number of nonzeros in - * each column of L and then constructs the Lp index array when it's done. The - * symbolic factorization does not need to do this in topological order. - * Compare ldl_symbolic with the first part of ldl_numeric, and note that the - * while (len > 0) loop is not present in ldl_symbolic. - * - * LDL Version 1.3, Copyright (c) 2006 by Timothy A Davis, - * University of Florida. All Rights Reserved. Developed while on sabbatical - * at Stanford University and Lawrence Berkeley National Laboratory. Refer to - * the README file for the License. Available at - * http://www.cise.ufl.edu/research/sparse. - */ - -#include "ldl.h" - -/* ========================================================================== */ -/* === ldl_symbolic ========================================================= */ -/* ========================================================================== */ - -/* The input to this routine is a sparse matrix A, stored in column form, and - * an optional permutation P. The output is the elimination tree - * and the number of nonzeros in each column of L. Parent [i] = k if k is the - * parent of i in the tree. The Parent array is required by ldl_numeric. - * Lnz [k] gives the number of nonzeros in the kth column of L, excluding the - * diagonal. - * - * One workspace vector (Flag) of size n is required. - * - * If P is NULL, then it is ignored. The factorization will be LDL' = A. - * Pinv is not computed. In this case, neither P nor Pinv are required by - * ldl_numeric. - * - * If P is not NULL, then it is assumed to be a valid permutation. If - * row and column j of A is the kth pivot, the P [k] = j. The factorization - * will be LDL' = PAP', or A (p,p) in MATLAB notation. The inverse permutation - * Pinv is computed, where Pinv [j] = k if P [k] = j. In this case, both P - * and Pinv are required as inputs to ldl_numeric. - * - * The floating-point operation count of the subsequent call to ldl_numeric - * is not returned, but could be computed after ldl_symbolic is done. It is - * the sum of (Lnz [k]) * (Lnz [k] + 2) for k = 0 to n-1. - */ - -void LDL_symbolic -( - LDL_int n, /* A and L are n-by-n, where n >= 0 */ - LDL_int Ap [ ], /* input of size n+1, not modified */ - LDL_int Ai [ ], /* input of size nz=Ap[n], not modified */ - LDL_int Lp [ ], /* output of size n+1, not defined on input */ - LDL_int Parent [ ], /* output of size n, not defined on input */ - LDL_int Lnz [ ], /* output of size n, not defined on input */ - LDL_int Flag [ ], /* workspace of size n, not defn. on input or output */ - LDL_int P [ ], /* optional input of size n */ - LDL_int Pinv [ ] /* optional output of size n (used if P is not NULL) */ -) -{ - LDL_int i, k, p, kk, p2 ; - if (P) - { - /* If P is present then compute Pinv, the inverse of P */ - for (k = 0 ; k < n ; k++) - { - Pinv [P [k]] = k ; - } - } - for (k = 0 ; k < n ; k++) - { - /* L(k,:) pattern: all nodes reachable in etree from nz in A(0:k-1,k) */ - Parent [k] = -1 ; /* parent of k is not yet known */ - Flag [k] = k ; /* mark node k as visited */ - Lnz [k] = 0 ; /* count of nonzeros in column k of L */ - kk = (P) ? (P [k]) : (k) ; /* kth original, or permuted, column */ - p2 = Ap [kk+1] ; - for (p = Ap [kk] ; p < p2 ; p++) - { - /* A (i,k) is nonzero (original or permuted A) */ - i = (Pinv) ? (Pinv [Ai [p]]) : (Ai [p]) ; - if (i < k) - { - /* follow path from i to root of etree, stop at flagged node */ - for ( ; Flag [i] != k ; i = Parent [i]) - { - /* find parent of i if not yet determined */ - if (Parent [i] == -1) Parent [i] = k ; - Lnz [i]++ ; /* L (k,i) is nonzero */ - Flag [i] = k ; /* mark i as visited */ - } - } - } - } - /* construct Lp index array from Lnz column counts */ - Lp [0] = 0 ; - for (k = 0 ; k < n ; k++) - { - Lp [k+1] = Lp [k] + Lnz [k] ; - } -} - - -/* ========================================================================== */ -/* === ldl_numeric ========================================================== */ -/* ========================================================================== */ - -/* Given a sparse matrix A (the arguments n, Ap, Ai, and Ax) and its symbolic - * analysis (Lp and Parent, and optionally P and Pinv), compute the numeric LDL' - * factorization of A or PAP'. The outputs of this routine are arguments Li, - * Lx, and D. It also requires three size-n workspaces (Y, Pattern, and Flag). - */ - -LDL_int LDL_numeric /* returns n if successful, k if D (k,k) is zero */ -( - LDL_int n, /* A and L are n-by-n, where n >= 0 */ - LDL_int Ap [ ], /* input of size n+1, not modified */ - LDL_int Ai [ ], /* input of size nz=Ap[n], not modified */ - double Ax [ ], /* input of size nz=Ap[n], not modified */ - LDL_int Lp [ ], /* input of size n+1, not modified */ - LDL_int Parent [ ], /* input of size n, not modified */ - LDL_int Lnz [ ], /* output of size n, not defn. on input */ - LDL_int Li [ ], /* output of size lnz=Lp[n], not defined on input */ - double Lx [ ], /* output of size lnz=Lp[n], not defined on input */ - double D [ ], /* output of size n, not defined on input */ - double Y [ ], /* workspace of size n, not defn. on input or output */ - LDL_int Pattern [ ],/* workspace of size n, not defn. on input or output */ - LDL_int Flag [ ], /* workspace of size n, not defn. on input or output */ - LDL_int P [ ], /* optional input of size n */ - LDL_int Pinv [ ] /* optional input of size n */ -) -{ - double yi, l_ki ; - LDL_int i, k, p, kk, p2, len, top ; - for (k = 0 ; k < n ; k++) - { - /* compute nonzero Pattern of kth row of L, in topological order */ - Y [k] = 0.0 ; /* Y(0:k) is now all zero */ - top = n ; /* stack for pattern is empty */ - Flag [k] = k ; /* mark node k as visited */ - Lnz [k] = 0 ; /* count of nonzeros in column k of L */ - kk = (P) ? (P [k]) : (k) ; /* kth original, or permuted, column */ - p2 = Ap [kk+1] ; - for (p = Ap [kk] ; p < p2 ; p++) - { - i = (Pinv) ? (Pinv [Ai [p]]) : (Ai [p]) ; /* get A(i,k) */ - if (i <= k) - { - Y [i] += Ax [p] ; /* scatter A(i,k) into Y (sum duplicates) */ - for (len = 0 ; Flag [i] != k ; i = Parent [i]) - { - Pattern [len++] = i ; /* L(k,i) is nonzero */ - Flag [i] = k ; /* mark i as visited */ - } - while (len > 0) Pattern [--top] = Pattern [--len] ; - } - } - /* compute numerical values kth row of L (a sparse triangular solve) */ - D [k] = Y [k] ; /* get D(k,k) and clear Y(k) */ - Y [k] = 0.0 ; - for ( ; top < n ; top++) - { - i = Pattern [top] ; /* Pattern [top:n-1] is pattern of L(:,k) */ - yi = Y [i] ; /* get and clear Y(i) */ - Y [i] = 0.0 ; - p2 = Lp [i] + Lnz [i] ; - for (p = Lp [i] ; p < p2 ; p++) - { - Y [Li [p]] -= Lx [p] * yi ; - } - l_ki = yi / D [i] ; /* the nonzero entry L(k,i) */ - D [k] -= l_ki * yi ; - Li [p] = k ; /* store L(k,i) in column form of L */ - Lx [p] = l_ki ; - Lnz [i]++ ; /* increment count of nonzeros in col i */ - } - if (D [k] == 0.0) return (k) ; /* failure, D(k,k) is zero */ - } - return (n) ; /* success, diagonal of D is all nonzero */ -} - - -/* ========================================================================== */ -/* === ldl_lsolve: solve Lx=b ============================================== */ -/* ========================================================================== */ - -void LDL_lsolve -( - LDL_int n, /* L is n-by-n, where n >= 0 */ - double X [ ], /* size n. right-hand-side on input, soln. on output */ - LDL_int Lp [ ], /* input of size n+1, not modified */ - LDL_int Li [ ], /* input of size lnz=Lp[n], not modified */ - double Lx [ ] /* input of size lnz=Lp[n], not modified */ -) -{ - LDL_int j, p, p2 ; - for (j = 0 ; j < n ; j++) - { - p2 = Lp [j+1] ; - for (p = Lp [j] ; p < p2 ; p++) - { - X [Li [p]] -= Lx [p] * X [j] ; - } - } -} - - -/* ========================================================================== */ -/* === ldl_dsolve: solve Dx=b ============================================== */ -/* ========================================================================== */ - -void LDL_dsolve -( - LDL_int n, /* D is n-by-n, where n >= 0 */ - double X [ ], /* size n. right-hand-side on input, soln. on output */ - double D [ ] /* input of size n, not modified */ -) -{ - LDL_int j ; - for (j = 0 ; j < n ; j++) - { - X [j] /= D [j] ; - } -} - - -/* ========================================================================== */ -/* === ldl_ltsolve: solve L'x=b ============================================ */ -/* ========================================================================== */ - -void LDL_ltsolve -( - LDL_int n, /* L is n-by-n, where n >= 0 */ - double X [ ], /* size n. right-hand-side on input, soln. on output */ - LDL_int Lp [ ], /* input of size n+1, not modified */ - LDL_int Li [ ], /* input of size lnz=Lp[n], not modified */ - double Lx [ ] /* input of size lnz=Lp[n], not modified */ -) -{ - int j, p, p2 ; - for (j = n-1 ; j >= 0 ; j--) - { - p2 = Lp [j+1] ; - for (p = Lp [j] ; p < p2 ; p++) - { - X [j] -= Lx [p] * X [Li [p]] ; - } - } -} - - -/* ========================================================================== */ -/* === ldl_perm: permute a vector, x=Pb ===================================== */ -/* ========================================================================== */ - -void LDL_perm -( - LDL_int n, /* size of X, B, and P */ - double X [ ], /* output of size n. */ - double B [ ], /* input of size n. */ - LDL_int P [ ] /* input permutation array of size n. */ -) -{ - LDL_int j ; - for (j = 0 ; j < n ; j++) - { - X [j] = B [P [j]] ; - } -} - - -/* ========================================================================== */ -/* === ldl_permt: permute a vector, x=P'b =================================== */ -/* ========================================================================== */ - -void LDL_permt -( - LDL_int n, /* size of X, B, and P */ - double X [ ], /* output of size n. */ - double B [ ], /* input of size n. */ - LDL_int P [ ] /* input permutation array of size n. */ -) -{ - LDL_int j ; - for (j = 0 ; j < n ; j++) - { - X [P [j]] = B [j] ; - } -} - - -/* ========================================================================== */ -/* === ldl_valid_perm: check if a permutation vector is valid =============== */ -/* ========================================================================== */ - -LDL_int LDL_valid_perm /* returns 1 if valid, 0 otherwise */ -( - LDL_int n, - LDL_int P [ ], /* input of size n, a permutation of 0:n-1 */ - LDL_int Flag [ ] /* workspace of size n */ -) -{ - LDL_int j, k ; - if (n < 0 || !Flag) - { - return (0) ; /* n must be >= 0, and Flag must be present */ - } - if (!P) - { - return (1) ; /* If NULL, P is assumed to be the identity perm. */ - } - for (j = 0 ; j < n ; j++) - { - Flag [j] = 0 ; /* clear the Flag array */ - } - for (k = 0 ; k < n ; k++) - { - j = P [k] ; - if (j < 0 || j >= n || Flag [j] != 0) - { - return (0) ; /* P is not valid */ - } - Flag [j] = 1 ; - } - return (1) ; /* P is valid */ -} - - -/* ========================================================================== */ -/* === ldl_valid_matrix: check if a sparse matrix is valid ================== */ -/* ========================================================================== */ - -/* This routine checks to see if a sparse matrix A is valid for input to - * ldl_symbolic and ldl_numeric. It returns 1 if the matrix is valid, 0 - * otherwise. A is in sparse column form. The numerical values in column j - * are stored in Ax [Ap [j] ... Ap [j+1]-1], with row indices in - * Ai [Ap [j] ... Ap [j+1]-1]. The Ax array is not checked. - */ - -LDL_int LDL_valid_matrix -( - LDL_int n, - LDL_int Ap [ ], - LDL_int Ai [ ] -) -{ - LDL_int j, p ; - if (n < 0 || !Ap || !Ai || Ap [0] != 0) - { - return (0) ; /* n must be >= 0, and Ap and Ai must be present */ - } - for (j = 0 ; j < n ; j++) - { - if (Ap [j] > Ap [j+1]) - { - return (0) ; /* Ap must be monotonically nondecreasing */ - } - } - for (p = 0 ; p < Ap [n] ; p++) - { - if (Ai [p] < 0 || Ai [p] >= n) - { - return (0) ; /* row indices must be in the range 0 to n-1 */ - } - } - return (1) ; /* matrix is valid */ -} |