{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Transpose Upper Triangular Matrix Vector Multiply Routines"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook walks you through how to implement $ x := U^T x $ where $ U $ is upper triangular. Vector $ y $ is not to be touched (and, indeed, not even passed into the routines). This is a little trickier than you might think. You may want to do a few small problems by hand if you don't get the right answer. Also, PictureFLAME may help you see what is going on."
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Getting started"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will use some functions that are part of our laff library (of which this function will become a part) as well as some routines from the FLAME API (Application Programming Interface) that allows us to write code that closely resembles how we typeset algorithms using the FLAME notation. These functions are imported with the \"import laff as laff\" and \"import flame\" statements."
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Algorithm that takes dot products"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"The routine
Trmv_ut_unb_var1( U, x )
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This routine, given upper triangular $ U \\in \\mathbb{R}^{n \\times n} $ and $ x \\in \\mathbb{R}^n $ computes $ x := U^T x $. The \"_ut_\" in the name of the routine indicates this is the \"upper, transpose\" matrix-vector multiplication.\n",
"\n",
"The specific laff functions we will use are \n",
"
laff.dots( x, y, alpha )
which computes $ \\alpha := x^T y + \\alpha $. laff.scal( alpha, x )
which computes $ x := \\alpha x $. Trmv_ut_unb_var2( U, x )
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This routine, given upper triangular $ U \\in \\mathbb{R}^{n \\times n} $ and $ x \\in \\mathbb{R}^n $ computes $ x := U^T x $. The \"_ut_\" in the name of the routine indicates this is the \"upper triangular, transpose\" matrix-vector multiplication. \n",
"\n",
"The specific laff functions we will use are \n",
" laff.axpy( alpha, x, y )
which computes $ y := \\alpha x + y $. laff.scal( alpha, x )
which computes $ x := \\alpha x $.