LAST Documentation

Linear Algebra Symbolic Toolbox

Authors

Affiliation

Davide Stocco

University of Trento (Italy)

Matteo Larcher

University of Trento (Italy)

Enrico Bertolazzi

University of Trento (Italy)

This is a module for the LAST (Linear Algebra Symbolic Toolbox) module. It contains the functions to solve linear systems of equations with large symbolic expressions. The module uses symbolic full pivoting LU and QR decompositions to solve linear systems. The ‘LEM’ (Large Expressions Management) module is used to avoid expression swell.

The following code is hopefully an improved version of the LULEM package described in the following PhD thesis:

Wenqin Zhou, Symbolic Computation Techniques for Solveing Large Expressions Problems from Mathematics and Engineering (2007), Faculty of Graduate Studies, The University of Western Ontario London, Ontario, Canada.

We would like to thank Jacques Carette for providing the original code that have inspired this module.

1 Installation

Download the package from the GitHub repository, release the zip file, and follow the instructions below. Optionally, you can clone the repository using the following command:

git clone https://github.com/StoccoDavide/LAST.git

1.1 Maple

To install the module you must have first installed Maple (2020 or later). Then open the PackAndGo.mw file and use the !!! button to execute the entire worksheet.

Then test the module in a Maple worksheet or document by executing LAST:-Info() or Describe(LAST). Alternatively, you can use one of the test files provided in the maple/tests folder. If the module is loaded without errors, it is done!

LEM Package

LEM is mandatory for the LAST module to work. However, they are highly recommended to facilitate the symbolic manipulation of the FEM system.. These packages are not included in the maple folder and must be downloaded separately from the LEM GitHub repository and LAST GitHub repository. Similarly as before, you can clone the repositories using the following command:

git clone https://github.com/StoccoDavide/LEM.git

The installation of these optinal packages is similar to the one described above and requires the execution of the PackAndGo.mw file in the respective library folders.

🚧 Attention! 🚧

Both LEM and LAST packages are written to work in an object-oriented programming style. Please note that Maple object-oriented programming features have slightly changed in 2021, which online documentation states:

As of Maple 2021, if the method has a formal parameter named _self, references to its object’s local or exported variables may be written without prefixing them. That is, _self:-variable may be written as just variable. Maple will add the self:- prefix internally when the method is simplified.

As of Maple 2021, a message-passing form of method call can be used, which will automatically pass the object as an argument if the method has a formal parameter named _self.

Another way to invoke a method, similar to that used in other object-oriented languages, was introduced in Maple 2021. In this form, the object name is qualified by the method name, object_name:-method_name(argument) just as it can be in the function mechanism described above. However, the object can be omitted from the argument sequence.

For further information please refer to the following link.

2 License

BSD 3-Clause License

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

3 Usage

In case you have no time to read through all the APIs and realize how the toolbox should or should not work, refer to the files prensent in maple/tests folder. This contains usage examples with increasing complexity and detail.

4 Maple API

4.1 Module Utilities

Info

Print module information.

Inputs: None.
Optional inputs: None.
Returns: NULL.

Proto: Info()

ModuleLoad

Module load procedure.

Inputs: None.
Optional inputs: None.
Returns: NULL.

Proto: ModuleLoad()

ModuleUnload

Module unload procedure.

Inputs: None.
Optional inputs: None.
Returns: NULL.

Proto: ModuleLoad()

ModuleCopy

Copy the object proto.

Inputs: _self::LAST, proto::LAST.
Optional inputs: None.
Returns: anything.

Proto: _self:-ModuleCopy(_self, proto)

CheckInit

Check if the LAST object is correctly initialized.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-CheckInit(_self)

InitLEM

Initialize the LEM object with veiling label label.

Inputs: _self::LAST, label::{string, symbol} := NULL.
Optional inputs: None.
Returns: NULL.

Proto: _self:-InitLEM(_self, label)

ClearLEM

Clear the LEM object.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-ClearLEM(_self)

SetLEM

Set the LEM object obj.

Inputs: _self::LAST, obj::LEM.
Optional inputs: None.
Returns: NULL.

Proto: _self:-SetLEM(_self, obj)

GetLEM

Get the LEM object.

Inputs: _self::LAST.
Optional inputs: None.
Returns: LEM.

Proto: _self:-GetLEM(_self)

EnableVerboseMode

Enable the verbosity of the module.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-EnableVerboseMode(_self)

DisableVerboseMode

Disable the verbosity of the module.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-DisableVerboseMode(_self)

SetVerboseMode

Set the verbosity of the module to mode.

Inputs: _self::LAST, mode::boolean.
Optional inputs: None.
Returns: NULL.

Proto: _self:-SetVerboseMode(_self, mode)

EnableWarningMode

Enable the warning mode of the module.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-EnableWarningMode(_self)

DisableWarningMode

Disable the warning mode of the module.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-DisableWarningMode(_self)

SetWarningMode

Set the warning mode of the module to mode.

Inputs: _self::LAST, mode::boolean.
Optional inputs: None.
Returns: NULL.

Proto: _self:-SetWarningMode(_self, mode)

SetTimeLimit

Set the time limit of the module to x.

Inputs: _self::LAST, x::numeric.
Optional inputs: None.
Returns: NULL.

Proto: _self:-SetTimeLimit(_self, x)

GetTimeLimit

Get the time limit of the module.

Inputs: _self::LAST.
Optional inputs: None.
Returns: numeric.

Proto: _self:-GetTimeLimit(_self)

EnableUnveiling

Enable the unveiling of expressions during factorization (longer computation time, possibly more accurate results).

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-EnableUnveiling(_self)

DisableUnveiling

Disable the unveiling of expressions during factorization (shorter computation time, possibly less accurate results).

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-DisableUnveiling(_self)

EnableFastPivoting

Enable fast pivoting during the factorization (first non-zero pivot is selected).

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-EnableFastPivoting(_self)

DisableFastPivoting

Disable fast pivoting during the factorization (best pivot is selected).

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-DisableFastPivoting(_self)

SetStoredData

Set the stored data of the module to data.

Inputs: _self::LAST, data::{list('='), set('=')}.
Optional inputs: None.
Returns: NULL.

Proto: _self:-SetStoredData(_self, data)

GetStoredData

Get the stored data of the module.

Inputs: _self::LAST.
Optional inputs: None.
Returns: {list('='), set('=')}.

Proto: _self:-GetStoredData(_self)

4.2 Module Interface

CheckResults

Check if the results of the last factorization are available.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-CheckResults(_self)

GetResults

Get the results of the last factorization. If field is specified, only the field Results['field'] is returned.

Inputs: _self::LAST, field::string := "all".
Optional inputs: None.
Returns: anything.

Proto: _self:-GetResults(_self, field)

ClearResults

Clear the results of the last factorization.

Inputs: _self::LAST.
Optional inputs: None.
Returns: NULL.

Proto: _self:-ClearResults(_self)

SolveLinearSystem

Solve the factorized linear system.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: NULL.

Proto: _self:-SolveLinearSystem(_self, b)

ApplyLP

Apply L^(-1)*P to the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-ApplyLP(_self, b)

GetUQT

Return the matrix U^T*Q.

Inputs: _self::LAST.
Optional inputs: None.
Returns: Matrix.

Proto: _self:-GetUQT(_self)

Spy

Plot of non-zero values of the matrix A.

Inputs: _self::LAST, A::Matrix.
Optional inputs: None.
Returns: anything.

Proto: _self:-Spy(_self, A)

GCD

Compute the greatest common divisor of the elements of the expression expr.

Inputs: _self::LAST, expr::{Matrix, Vector, list}, postproc::boolean := true.
Optional inputs: None.
Returns: algebraic.

Proto: _self:-GCD(_self, expr, postproc)

SpyLU

Plot of non-zero values of the matrices A, L and U with fill-in values.

Inputs: _self::LAST, A::Matrix, L::Matrix, U::Matrix.
Optional inputs: None.
Returns: anything.

Proto: _self:-SpyLU(_self, A, L, U)

SpyFFLU

Plot of non-zero values of the matrices A, M with fill-in values.

Inputs: _self::LAST, A::Matrix, M::Matrix.
Optional inputs: None.
Returns: anything.

Proto: _self:-SpyFFLU(_self, A, M)

PermutationMatrices

Compute the LU decomposition permutation matrices provided the rows pivot vector r and the columns pivot vector c.

Inputs: _self::LAST, r::Vector(nonnegint), c::Vector(nonnegint).
Optional inputs: None.
Returns: Matrix(nonnegint).

Proto: _self:-PermutationMatrices(_self, r, c)

RowPermutationMatrix

Compute the row permutation matrix provided the pivot vector r.

Inputs: _self::LAST, r::Vector(nonnegint).
Optional inputs: None.
Returns: Matrix.

Proto: _self:-RowPermutationMatrix(_self, r)

ColPermutationMatrix

Compute the column permutation matrix provided the pivot vector c.

Inputs: _self::LAST, c::Vector(nonnegint).
Optional inputs: None.
Returns: Matrix.

Proto: _self:-ColPermutationMatrix(_self, c)

Rank

Compute the rank of a square matrix A by transforming it in row echelon form. If ref is true, the matrix is transformed in reduced row echelon form. Notice that the rank does not modify the previously stored factorization results.

Inputs: _self::LAST, A::Matrix.
Optional inputs: rref := false.
Returns: NULL.

Proto: _self:-Rank(_self, A, rref = false)

Pivoting

Compute the LU decomposition pivots vectors with minimum degree provided the step k, the temporary LU (NAG) matrix M, the rows permutation r and the columns permutation c.

Inputs: _self::LAST, k::integer, M::Matrix, r::Vector(nonnegint), c::Vector(nonnegint).
Optional inputs: None.
Returns: table.

Proto: _self:-Pivoting(_self, k, M, r, c)

PivotCost

Compute the cost of the pivot x.

Inputs: _self::LAST, x::algebraic.
Optional inputs: None.
Returns: integer.

Proto: _self:-PivotCost(_self, x)

GetDegrees

Get the degree matrices of the matrix A.

Inputs: _self::LAST, A::Matrix.
Optional inputs: None.
Returns: Matrix(nonnegint).

Proto: _self:-GetDegrees(_self, A)

DegreeCost

Set the strategy val for the minimum degree ordering.

Inputs: _self::LAST, val::table.
Optional inputs: None.
Returns: integer.

Proto: _self:-DegreeCost(_self, val)

PivotingCompare

Compute the pivoting strategy: given the current pivot cur and the next pivot val, decide if the next pivot is better than the current pivot or not.

Inputs: _self::LAST, cur::table, val::table.
Optional inputs: None.
Returns: boolean.

Proto: _self:-PivotingCompare(_self, cur, val)

LU

Compute the LU decomposition of a square matrix A and check if the veiling symbol is already present in the matrix coefficients.

Inputs: _self::LAST, A::Matrix.
Returns: NULL.

Proto: _self:-LU(_self, A)

LUsolve

Solve the linear system Ax=b using LU decomposition provided the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-LUsolve(_self, b)

LUapplyLP

Apply L^(-1)*P to the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-LUapplyLP(_self, b)

LUgetUQT

Return the matrix U^T*Q.

Inputs: _self::LAST.
Optional inputs: None.
Returns: Matrix.

Proto: _self:-LUgetUQT(_self)

FFLU

Compute the Fraction-Free LU (FFLU) decomposition of a square matrix A.

Inputs: _self::LAST, A::Matrix.
Optional inputs: None.
Returns: NULL.

Proto: _self:-FFLU(_self, A)

FFLUsolve

Apply L^(-1)*P to the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-FFLUsolve(_self, b)

FFLUapplyLP

Apply L^(-1)*P to the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-FFLUapplyLP(_self, b)

FFLUgetUQT

Return the matrix U^T*Q.

Inputs: _self::LAST.
Optional inputs: None.
Returns: Matrix.

Proto: _self:-FFLUgetUQT(_self)

FFLUgetLU

Return the matrix L and U such that P.A.Q = L.U.

Inputs: _self::LAST.
Optional inputs: None.
Returns: Matrix.

Proto: _self:-FFLUgetLU(_self)

GJ

Compute the Gauss-Jordan decomposition of a rectangular matrix A.

Inputs: _self::LAST, A::Matrix.
Optional inputs: None.
Returns: NULL.

Proto: _self:-GJ(_self, A)

GJsolve

Solve the linear system Ax=b using GJ decomposition provided the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-GJsolve(_self, b)

QR

Compute the Givens QR decomposition of a square matrix A and check if the veiling symbol is already present in the matrix coefficients.

Inputs: _self::LAST, A::Matrix.
Optional inputs: None.
Returns: NULL.

Proto: _self:-QR(_self, A)

QRsolve

Solve the linear system Ax=b using QR decomposition provided the vector b.

Inputs: _self::LAST, b::Vector.
Optional inputs: None.
Returns: Vector.

Proto: _self:-QRsolve(_self, b)